perm filename V231.XGP[TEX,DEK]1 blob sn#407104 filedate 1979-01-01 generic text, type T, neo UTF8
/LMAR=50/TMAR=50/RMAR=4095/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=0000070*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β	←␈↓ α6␈εαSECTION␈α3.1␈αof␈αTHE␈αAR␈α⎇T␈αOF␈αCOMPUTER␈αPR␈α␈OGRAMMING
␈β

␈↓ β%␈ε⊗⎇␈εα␈α1978␈αAddison↑Wesley␈αPublishing␈αCompan␈α␈y,␈αInc.
␈β⊃L␈↓ ε2␈ε∧0
␈β∪(

␈β↓l␈↓ ↓H␈∧↓l↓H↓(␈↓ ¬␈∧↓l¬↓(
␈β↓m␈↓ ↓H␈∧↓m↓H(↓␈↓ ,␈∧↓m,(↓
␈βαN␈↓ ↓H␈ε≡C␈α∧H␈α∧A␈α∧P␈αβT␈α∧E␈αβR␈α%T␈αβH␈α∧R␈α∧E␈α∧E
␈ββ⎇␈↓ ε\␈ε≤RANDOM␈α∃NU␈α␈MBERS
␈β¬
␈↓ π$␈ε Any␈α␈one␈αwho␈αconsiders␈αarithmetical
␈β¬4␈↓ πλ␈ε methods␈αof␈αproducing␈αrandom␈αdigits
␈β¬\␈↓ πi␈ε is,␈αof␈αcourse,␈αin␈αa␈αstate␈αof␈αsin.
␈βε≤␈↓ π<␈ε∨←JOHN␈αV␈α␈ON␈αNEUMANN␈α(1951)
␈βε⎇␈↓ π~␈ε Lest␈αmen␈αsuspect␈αy␈α␈our␈αtale␈αuntrue,
␈βπ$␈↓ λ5␈ε Keep␈αprobability␈αin␈αview.
␈βπd␈↓ λq␈ε∨←JOHN␈αGA␈α⎇Y␈α(1727)
␈βλE␈↓ εb␈ε There␈αwanted␈αnot␈αsome␈αbeams␈αof␈αlight
␈βλl␈↓ ∧`␈ε to␈αguide␈αmen␈αin␈αthe␈αex␈α␈ercise␈αof␈αtheir␈αStocastick␈αfaculty.
␈β	,␈↓ λN␈ε∨←JOHN␈αO␈α␈WEN␈α(1662)
␈β
e␈↓ ↓H␈ε≥3␈α␈.1.␈α
I␈α↓NTRODUCTION
␈β+␈↓ ↓H␈εαN␈↓ αu␈εαthat␈α⊂are␈α∂\chosen␈α⊂at␈α⊂random"␈α∂are␈α⊂useful␈α∂in␈α⊂man␈α␈y␈α∂di{eren␈α␈t␈α⊂kinds␈α∂of
␈β0␈↓ ↓d␈ε∧UMBE␈α↓RS
␈βV␈↓ ↓H␈εαapplications.␈αFor␈αexample:
␈β⊃␈↓ ↓b␈εαa)␈↓ α␈ε∂Sim␈α␈ulation.␈εα␈α∪When␈α
a␈α	computer␈α
is␈α	being␈α
used␈α	to␈α	sim␈α␈ulate␈α
natural␈α	phenomena,
␈β<␈↓ ↓H␈εαrandom␈αn␈α␈um␈α␈bers␈α
are␈α
required␈α
to␈α
mak␈α␈e␈α
things␈αrealistic.␈α∂Sim␈α␈ulation␈α
co␈α␈v␈α␈ers␈αman␈α␈y
␈βg␈↓ ↓H␈εα|elds,␈αfrom␈αthe␈αstudy␈α
of␈αn␈α␈uclear␈αph␈α␈ysics␈α(where␈α
particles␈αare␈αsubject␈αto␈αrandom
␈β
∩␈↓ ↓H␈εαcollisions)␈α	to␈α
system␈α
engineering␈α
(where␈α	people␈α
come␈α
in␈α␈to,␈α
say,␈α
a␈α
bank␈α
at␈α	random
␈β
>␈↓ ↓H␈εαin␈α␈tervals).
␈β
x␈↓ ↓`␈εαb)␈↓ α␈ε∂Sampling.␈εα␈α∪It␈α	is␈α	often␈α	impractical␈α	to␈α
examine␈α	all␈α	possible␈α	cases,␈α
but␈α	a␈α	random
␈β∞#␈↓ ↓H␈εαsample␈αwill␈αpro␈α␈vide␈αinsigh␈α␈t␈αin␈α␈to␈αwhat␈αconstitutes␈α\typical"␈αbehavior.
␈β∞↑␈↓ ↓d␈εαc)␈↓ α␈ε∂Numerical␈α
analysis.␈εα␈α∃Ingenious␈α
techniques␈α
for␈α
solving␈α
complicated␈α
n␈α␈umerical
␈β∂	␈↓ ↓H␈εαproblems␈α∂hav␈α␈e␈α∂been␈α∂devised␈α∂using␈α∂random␈α⊂n␈α␈um␈α␈bers.␈α∃Sev␈α␈eral␈α∂books␈α∂hav␈α␈e␈α∂been
␈β∂5␈↓ ↓H␈εαwritten␈αon␈αthis␈αsubject.
␈β∂o␈↓ ↓`␈εαd)␈↓ α␈ε∂Computer␈α∞programming.␈εα␈α≥Random␈α∞values␈α∂mak␈α␈e␈α∞a␈α∞good␈α∞source␈α∞of␈α∞data␈α∞for
␈β⊂~␈↓ ↓H␈εαtesting␈α
the␈αe{ectiv␈α␈eness␈α
of␈αcomputer␈α
algorithms.␈αThis␈α
is␈α
the␈αprimary␈α
application
␈β⊂F␈↓ ↓H␈εαof␈α∂in␈α␈terest␈α⊂to␈α⊂us␈α⊂in␈α⊂this␈α∂series␈α⊂of␈α⊂books;␈α∩it␈α∂accoun␈α␈ts␈α⊂for␈α⊂the␈α⊂fact␈α⊂that␈α∂random
␈β⊂q␈↓ ↓H␈εαn␈α␈um␈α␈bers␈α	are␈α	already␈α	being␈α
considered␈α	here␈α	in␈α	Chapter␈α
3,␈α	before␈α
most␈α	of␈α	the␈α	other
␈β⊃≤␈↓ ↓H␈εαcomputer␈αalgorithms␈αhav␈α␈e␈αappeared.
␈β⊃L␈↓ ε2␈ε∧1
␈β∪(

␈β↓Y␈↓ ↓H␈εα2␈↓ α=␈ε∞RA␈α␈NDOM␈α	NUMBERS␈εα␈↓ 
}3.1
␈βα&␈↓ ↓d␈εαe)␈↓ α␈ε∂Decision␈αmaking.␈εα␈α→There␈αare␈αreports␈αthat␈αman␈α␈y␈αex␈α␈ecutiv␈α␈es␈αmak␈α␈e␈αtheir␈αdeci-
␈βαQ␈↓ ↓H␈εαsions␈αby␈α
⎇ipping␈α
a␈α
coin␈α
or␈αby␈α
thro␈α␈wing␈α
darts,␈α
etc.␈α∞It␈α
is␈α
also␈α
rumored␈α
that␈αsome
␈βα⎇␈↓ ↓H␈εαcollege␈α∞professors␈α
prepare␈α∞their␈α∞grades␈α∞on␈α∞such␈α∞a␈α∞basis.␈α∩Sometimes␈α∞it␈α∞is␈α
impor-
␈ββ(␈↓ ↓H␈εαtan␈α␈t␈α
to␈α
mak␈α␈e␈αa␈α
completely␈α
\un␈α␈biased"␈α
decision;␈αthis␈αability␈α
is␈α
occasionally␈α
useful
␈ββS␈↓ ↓H␈εαin␈α
computer␈α∞algorithms,␈α∞for␈α
example␈α∞in␈α∞situations␈α
where␈α∞a␈α
|x␈α␈ed␈α∞decision␈α
made
␈ββ}␈↓ ↓H␈εαeach␈αtime␈αw␈α␈ould␈αcause␈αthe␈αalgorithm␈αto␈αrun␈αmore␈αslo␈α␈wly.␈αRandomness␈αis␈αalso␈αan
␈β∧)␈↓ ↓H␈εαessen␈α␈tial␈αpart␈αof␈αoptimal␈αstrategies␈αin␈αthe␈αtheory␈αof␈αgames.
␈β∧d␈↓ ↓h␈εαf)␈↓ α␈ε∂Recreation.␈εα␈α_Rolling␈αdice,␈αsh␈α␈u␈␈ing␈αdecks␈αof␈αcards,␈αspinning␈αroulette␈αwheels,
␈β¬⊂␈↓ ↓H␈εαetc.,␈α∞are␈α∞fascinating␈α∞pastimes␈α∞for␈α∞just␈α∞about␈α∞ev␈α␈erybody.␈α∩These␈α
traditional␈α∞uses
␈β¬;␈↓ ↓H␈εαof␈αrandom␈αn␈α␈um␈α␈bers␈αhav␈α␈e␈αsuggested␈αthe␈αname␈α\Mon␈α␈te␈αCarlo␈αmethod,"␈αa␈αgeneral
␈β¬f␈↓ ↓H␈εαterm␈αused␈αto␈αdescribe␈αan␈α␈y␈αalgorithm␈αthat␈αemplo␈α␈ys␈αrandom␈αn␈α␈um␈α␈bers.
␈βε!␈↓ α␈εαPeople␈α
who␈α∞think␈α
about␈α
this␈α
topic␈α
almost␈α∞in␈α␈variably␈α
get␈α
in␈α␈to␈α
philosophical
␈βεL␈↓ ↓H␈εαdiscussions␈α
about␈α
what␈α
the␈α
w␈α␈ord␈α
\random"␈α
means.␈α∂In␈α
a␈α
sense,␈α
there␈α
is␈α
no␈α
such
␈βεw␈↓ ↓H␈εαthing␈α	as␈αλa␈α	random␈α	n␈α␈um␈α␈ber;␈α
for␈α	example,␈α
is␈αλ2␈α	a␈α	random␈α	n␈α␈um␈α␈ber?␈αRather,␈α
w␈α␈e␈αλspeak
␈βπ#␈↓ ↓H␈εαof␈αa␈ε∂␈αsequence␈αof␈αindependen␈α␈t␈αrandom␈αn␈α␈um␈α␈bers␈εα␈αwith␈αa␈αspeci|ed␈ε∂␈αdistribution␈εα,␈αand
␈βπN␈↓ ↓H␈εαthis␈α∂means␈α⊂loosely␈α⊂that␈α⊂each␈α⊂n␈α␈um␈α␈ber␈α∂was␈α⊂obtained␈α⊂merely␈α⊂by␈α⊂chance,␈α⊂having
␈βπy␈↓ ↓H␈εαnothing␈αto␈αdo␈αwith␈αother␈α
n␈α␈um␈α␈bers␈αof␈αthe␈αsequence,␈αand␈α
that␈αeach␈αn␈α␈um␈α␈ber␈αhas␈αa
␈βλ$␈↓ ↓H␈εαspeci|ed␈αprobability␈αof␈αfalling␈αin␈αan␈α␈y␈αgiv␈α␈en␈αrange␈αof␈αvalues.
␈βλQ␈↓ α␈εαA␈ε∂␈αλuniform␈εα␈α	distribution␈αλon␈αλa␈α	|nite␈αλset␈αλof␈α	n␈α␈um␈α␈bers␈αλis␈αλone␈αλin␈α	which␈αλeach␈αλpossible
␈βλ|␈↓ ↓H␈εαn␈α␈um␈α␈ber␈α
is␈α
equally␈α	probable.␈αA␈α
distribution␈α
is␈α
generally␈α
understood␈α
to␈α	be␈α
uniform
␈β	'␈↓ ↓H␈εαunless␈αsome␈αother␈αdistribution␈αis␈αspeci|cally␈αmen␈α␈tioned.
␈β	P␈↓ λz␈ε¬1
␈β	S␈↓ α␈εαEach␈α⊃of␈α⊂the␈α⊃ten␈α⊂digits␈α⊃0␈α⊃through␈α⊂9␈α⊃will␈α⊂occur␈α⊃about␈↓ 	$␈εαof␈α⊃the␈α⊂time␈α⊃in␈α⊂a
␈β	d␈↓ λs␈∧	dλsα≥
␈β	f␈↓ λs␈ε¬10
␈β	␈␈↓ ↓H␈εα(uniform)␈α
sequence␈α∞of␈α∞random␈α
digits.␈α⊃Each␈α∞pair␈α∞of␈α
t␈α␈w␈α␈o␈α∞successiv␈α␈e␈α∞digits␈α
should
␈β
'␈↓ β$␈ε¬1
␈β
*␈↓ ↓H␈εαoccur␈α
about␈↓ βR␈εαof␈α∞the␈α∞time,␈α∞etc.␈α∩Yet␈α∞if␈α∞w␈α␈e␈α
tak␈α␈e␈α∞a␈α∞truly␈α∞random␈α∞sequence␈α∞of␈α
a
␈β
:␈↓ β∃␈∧
:β∃α,
␈β
=␈↓ β∃␈ε¬1␈α↓00
␈β
U␈↓ ↓H␈εαmillion␈α
digits,␈α
it␈α
will␈α
not␈αalways␈α
hav␈α␈e␈α
exactly␈α
100,000␈α
zeros,␈α
100,000␈αones,␈α
etc.␈αIn
␈β␈↓ ↓H␈εαfact,␈α
chances␈α
of␈α
this␈α
are␈α
quite␈α
slim;␈α∞a␈ε∂␈α
sequence␈εα␈α
of␈α
such␈α
sequences␈α
will␈α
hav␈α␈e␈α
this
␈β+␈↓ ↓H␈εαcharacter␈αon␈αthe␈αav␈α␈erage.
␈βX␈↓ α␈εαAn␈α␈y␈α∞speci|ed␈α∞sequence␈α∞of␈α∞a␈α∞million␈α∞digits␈α∞is␈α∞equally␈α∞as␈α∞probable␈α∞as␈α
the␈α∞se-
␈ββ␈↓ ↓H␈εαquence␈αconsisting␈αof␈αa␈αmillion␈ε∂␈α
zeros.␈εα␈αTh␈α␈us,␈αif␈αw␈α␈e␈α
are␈αchoosing␈αa␈αmillion␈αdigits␈αat
␈β.␈↓ ↓H␈εαrandom␈αλand␈α	if␈αλthe␈α	|rst␈αλ999,999␈α	of␈αλthem␈α	happen␈αλto␈α	come␈αλout␈α	to␈αλbe␈α	zero,␈α	the␈αλchance
␈βV␈↓ ε[␈ε¬1
␈βY␈↓ ↓H␈εαthat␈αthe␈α|nal␈αdigit␈αis␈αzero␈αis␈αstill␈αexactly␈↓ εt␈εα,␈αin␈αa␈αtruly␈αrandom␈αsituation.␈αThese
␈βj␈↓ εT␈∧jεTα≥
␈βl␈↓ εT␈ε¬10
␈β
¬␈↓ ↓H␈εαstatemen␈α␈ts␈α	seem␈α
parado␈α␈xical␈α
to␈α	man␈α␈y␈α
people,␈α
but␈α
there␈α	is␈α
really␈α
no␈α	con␈α␈tradiction
␈β
0␈↓ ↓H␈εαhere.
␈β
\␈↓ α␈εαThere␈αare␈α
sev␈α␈eral␈αways␈αto␈α
form␈α␈ulate␈αdecen␈α␈t␈αabstract␈α
de|nitions␈αof␈αrandom-
␈β∞π␈↓ ↓H␈εαness,␈α∂and␈α∂w␈α␈e␈α∂will␈α∂return␈α∂to␈α∂this␈α∂in␈α␈teresting␈α∂subject␈α∞in␈α∂Section␈α∂3.5;␈α⊃but␈α∂for␈α∞the
␈β∞3␈↓ ↓H␈εαmomen␈α␈t,␈α
let␈α
us␈α
con␈α␈ten␈α␈t␈α
ourselv␈α␈es␈α
with␈α
an␈α
in␈α␈tuitiv␈α␈e␈α
understanding␈α
of␈α
the␈α
concept.
␈β∞n␈↓ α␈εαAt␈α
|rst,␈α
people␈αwho␈α
needed␈αrandom␈α
n␈α␈um␈α␈bers␈α
in␈αtheir␈α
scien␈α␈ti|c␈α
w␈α␈ork␈αw␈α␈ould
␈β∂→␈↓ ↓H␈εαdraw␈α∂balls␈α∂out␈α∂of␈α∂a␈α∂\w␈α␈ell-stirred␈α∂urn"␈α∂or␈α∂w␈α␈ould␈α⊂roll␈α∂dice␈α∂or␈α∂deal␈α∂out␈α∂cards.␈α∃A
␈β∂D␈↓ ↓H␈εαtable␈αof␈αo␈α␈v␈α␈er␈α40,000␈αrandom␈αdigits,␈α\tak␈α␈en␈αat␈αrandom␈αfrom␈αcensus␈αreports,"␈αwas
␈β∂o␈↓ ↓H␈εαpublished␈α∞in␈α∂1927␈α∞by␈α∂L.␈α∂H.␈α∞C.␈α∂Tippett.␈α∪Since␈α∂then,␈α∂a␈α∂n␈α␈um␈α␈ber␈α∞of␈α∂devices␈α∞hav␈α␈e
␈β⊂~␈↓ ↓H␈εαbeen␈α	built␈α
to␈α
generate␈α	random␈α
n␈α␈um␈α␈bers␈α	mechanically;␈αthe␈α
|rst␈α	such␈α
machine␈α	was
␈β⊂F␈↓ ↓H␈εαused␈α∞in␈α∞1939␈α∞by␈α∞M.␈α∞G.␈α∞Kendall␈α∞and␈α∞B.␈α∞Babington-Smith␈α∞to␈α∞produce␈α∞a␈α∞table␈α∞of
␈β⊂q␈↓ ↓H␈εα100,000␈α∂random␈α∂digits,␈α⊂and␈α∂in␈α∂1955␈α∂the␈α∂RAND␈α∂Corporation␈α∂published␈α∂a␈α∂w␈α␈ell-
␈β⊃≤␈↓ ↓H␈εαkno␈α␈wn␈α
table␈α
of␈αa␈α
million␈α
random␈α
digits␈αobtained␈α
with␈α
the␈αhelp␈α
of␈α
another␈α
special
␈β∪(

␈β↓Y␈↓ ↓H␈εα3.1␈ε∞␈↓ λYINTR␈α␈ODUCT␈α␈ION␈↓ ~␈εα3
␈βα(␈↓ ↓H␈εαdevice.␈αA␈αfamous␈αrandom-n␈α␈um␈α␈ber␈αmachine␈αcalled␈αERNIE␈αhas␈αbeen␈αused␈αto␈αpick
␈βαS␈↓ ↓H␈εαthe␈α∞winning␈α∂n␈α␈um␈α␈bers␈α∞in␈α∂the␈α∞British␈α∂Premium␈α∞Savings␈α∂Bonds␈α∞lottery.␈α≡[See␈α∞the
␈βα}␈↓ ↓H␈εαarticles␈α∞by␈α∞Kendall␈α∂and␈α∞Babington-Smith␈α∞in␈ε∂␈α∂J.␈α∞Ro␈α␈yal␈α∞Stat.␈α∂Soc.␈εα,␈α∂Series␈α∞A,␈ε∩␈α∞101
␈ββ*␈↓ ↓H␈εα(1938),␈α147↑166,␈αand␈αSeries␈αB,␈ε∩␈α6␈εα␈α(1939),␈α51↑61;␈αsee␈αalso␈αthe␈αreview␈αof␈αthe␈αRAND
␈ββU␈↓ ↓H␈εαtable␈αin␈ε∂␈αMath.␈α
Comp.␈ε∩␈α10␈εα␈α
(1956),␈α39↑43,␈α
and␈αthe␈αdiscussion␈α
of␈αERNIE␈α
by␈αW.␈αE.
␈β∧␈↓ ↓H␈εαThomson␈αet␈αal.,␈ε∂␈αJ.␈αRo␈α␈yal␈αStat.␈αSoc.␈εα,␈αSeries␈αA,␈ε∩␈α122␈εα␈α(1959),␈α301↑333.]
␈β∧,␈↓ α␈εαShortly␈α
after␈α	computers␈α
w␈α␈ere␈α
in␈α␈troduced,␈α
people␈α
began␈α	to␈α
search␈α
for␈α	e}cien␈α␈t
␈β∧W␈↓ ↓H␈εαways␈α	to␈α	obtain␈α	random␈α
n␈α␈um␈α␈bers␈α	within␈α	computer␈α	programs.␈αA␈α
table␈α	can␈α	be␈α	used,
␈β¬α␈↓ ↓H␈εαbut␈α	this␈α
method␈α
is␈α
of␈α	limited␈α
utility␈α
because␈α
of␈α
the␈α	memory␈α
space␈α
and␈α
input␈α	time
␈β¬-␈↓ ↓H␈εαrequiremen␈α␈t,␈α∂because␈α⊂the␈α∂table␈α∂may␈α∂be␈α∂too␈α∂short,␈α⊂and␈α∂because␈α∂it␈α∂is␈α∂a␈α∂bit␈α∂of␈α∂a
␈β¬Y␈↓ ↓H␈εαn␈α␈uisance␈αto␈αprepare␈αand␈αmain␈α␈tain␈αthe␈αtable.␈αMachines␈αsuch␈αas␈αERNIE␈αmigh␈α␈t␈αbe
␈βε∧␈↓ ↓H␈εαattached␈α∂to␈α∂the␈α⊂computer,␈α⊂but␈α∂this␈α∂w␈α␈ould␈α⊂be␈α∂unsatisfactory␈α∂since␈α⊂it␈α∂w␈α␈ould␈α∂be
␈βε/␈↓ ↓H␈εαimpractical␈α
to␈α
reproduce␈α
calculations␈α
exactly␈α
a␈α
second␈α
time␈α
when␈α
checking␈α
out
␈βεZ␈↓ ↓H␈εαa␈αprogram;␈αand␈αsuch␈αmachines␈αhav␈α␈e␈αtended␈αto␈αsu{er␈αfrom␈αmalfunctions␈αthat␈αare
␈βπ¬␈↓ ↓H␈εαdi}cult␈αto␈αdetect.
␈βπ1␈↓ α␈εαThe␈α
inadequacy␈α
of␈α	these␈α
methods␈α
led␈α
to␈α
an␈α	in␈α␈terest␈α
in␈α
the␈α
production␈α
of␈α	ran-
␈βπ]␈↓ ↓H␈εαdom␈α	n␈α␈um␈α␈bers␈α
using␈α	the␈α	arithmetic␈α
operations␈α	of␈α
a␈α	computer.␈αJohn␈α	v␈α␈on␈α	Neumann
␈βλλ␈↓ ↓H␈εα|rst␈αsuggested␈αthis␈αapproach␈α
in␈αabout␈α1946,␈α
using␈αthe␈α\middle-square"␈αmethod.
␈βλ3␈↓ ↓H␈εαHis␈αidea␈α
was␈α
to␈α
tak␈α␈e␈α
the␈α
square␈α
of␈αthe␈α
previous␈α
random␈α
n␈α␈um␈α␈ber␈α
and␈α
to␈αextract
␈βλ↑␈↓ ↓H␈εαthe␈α∂middle␈α∂digits;␈α⊂for␈α∂example,␈α⊂if␈α∂w␈α␈e␈α∂are␈α∂generating␈α∂10-digit␈α∂n␈α␈um␈α␈bers␈α∞and␈α∂the
␈β		␈↓ ↓H␈εαprevious␈αvalue␈αwas␈α5772156649,␈αw␈α␈e␈αsquare␈αit␈αto␈αget
␈β	b␈↓ ¬↓␈εα33317792380594909201,
␈β
:␈↓ ↓H␈εαand␈αthe␈αnext␈αn␈α␈um␈α␈ber␈αis␈αtherefore␈α7923805949.
␈β
f␈↓ α␈εαThere␈α∂is␈α∂a␈α∂fairly␈α∂obvious␈α∞objection␈α∂to␈α∂this␈α∂technique:␈α∩ho␈α␈w␈α∂can␈α∂a␈α∞sequence
␈β⊃␈↓ ↓H␈εαgenerated␈α
in␈α	such␈α
a␈α
way␈α
be␈α
random,␈α
since␈α
each␈α
n␈α␈um␈α␈ber␈α
is␈α
completely␈α	determined
␈β<␈↓ ↓H␈εαby␈α
its␈α
predecessor?␈αThe␈αansw␈α␈er␈α
is␈α
that␈α
this␈α
sequence␈ε∂␈α
isn't␈εα␈αrandom,␈α
but␈α
it␈ε∂␈α
appears
␈βh␈↓ ↓H␈εαto␈α
be.␈αIn␈α
typical␈α
applications␈αthe␈α
actual␈α
relationship␈α
bet␈α␈w␈α␈een␈α
one␈α
n␈α␈um␈α␈ber␈α
and␈α
its
␈β∪␈↓ ↓H␈εαsuccessor␈απhas␈απno␈απph␈α␈ysical␈απsigni|cance;␈α	hence␈απthe␈απnonrandom␈απcharacter␈απis␈απnot␈απreally
␈β>␈↓ ↓H␈εαundesirable.␈αIn␈α␈tuitiv␈α␈ely,␈αthe␈αmiddle␈αsquare␈αseems␈αto␈αbe␈αa␈αfairly␈αgood␈αscram␈α␈bling
␈βi␈↓ ↓H␈εαof␈αthe␈αprevious␈αn␈α␈um␈α␈ber.
␈β
∃␈↓ α␈εαSequences␈α∞generated␈α
in␈α∞a␈α∞deterministic␈α
way␈α∞such␈α∞as␈α
this␈α∞are␈α∞usually␈α
called
␈β
@␈↓ ↓H␈ε∂pseudo-random␈εα␈αor␈ε∂␈αquasi-random␈εα␈α
sequences␈αin␈αthe␈α
high␈α␈bro␈α␈w␈αtechnical␈αliterature,
␈β
k␈↓ ↓H␈εαbut␈α∞in␈α∞this␈α
book␈α∞w␈α␈e␈α∞shall␈α∞simply␈α∞call␈α∞them␈α∞random␈α∞sequences,␈α∂with␈α
the␈α∞under-
␈β∞↔␈↓ ↓H␈εαstanding␈α∂that␈α∂they␈α∂only␈ε∂␈α⊂appear␈εα␈α∂to␈α∂be␈α∂random.␈α⊗Being␈α∂\apparen␈α␈tly␈α∂random"␈α∂is
␈β∞B␈↓ ↓H␈εαperhaps␈α
all␈αthat␈α
can␈αbe␈α
said␈αabout␈α
an␈α␈y␈αrandom␈α
sequence␈α
an␈α␈yway.␈αRandom␈α
n␈α␈um-
␈β∞m␈↓ ↓H␈εαbers␈αgenerated␈αdeterministically␈αon␈α
computers␈αhav␈α␈e␈αw␈α␈ork␈α␈ed␈α
quite␈αw␈α␈ell␈αin␈αnearly
␈β∂_␈↓ ↓H␈εαev␈α␈ery␈αλapplication,␈αλpro␈α␈vided␈αλthat␈αλa␈αλsuitable␈αλmethod␈αλhas␈αλbeen␈αλcarefully␈αλselected.␈α
Of
␈β∂C␈↓ ↓H␈εαcourse,␈αλdeterministic␈αλsequences␈αλaren't␈απalways␈αλthe␈αλansw␈α␈er;␈α	they␈αλcertainly␈απshouldn't
␈β∂o␈↓ ↓H␈εαreplace␈αERNIE␈αfor␈αthe␈αlotteries.
␈β⊂~␈↓ α␈εαVon␈αNeumann's␈αoriginal␈α\middle-square␈αmethod"␈αhas␈αactually␈αpro␈α␈v␈α␈ed␈αto␈αbe
␈β⊂F␈↓ ↓H␈εαa␈αλcomparativ␈α␈ely␈α	poor␈α	source␈α	of␈α	random␈αλn␈α␈um␈α␈bers.␈αThe␈α	danger␈α	is␈α	that␈α	the␈αλsequence
␈β⊂q␈↓ ↓H␈εαtends␈αto␈αget␈αin␈α␈to␈αa␈αrut,␈αa␈αshort␈αcy␈α␈cle␈αof␈αrepeating␈αelemen␈α␈ts.␈αFor␈αexample,␈αif␈αzero
␈β⊃≤␈↓ ↓H␈εαev␈α␈er␈αappears␈αas␈αa␈αn␈α␈um␈α␈ber␈αof␈αthe␈αsequence,␈αit␈αwill␈αcon␈α␈tin␈α␈ually␈αperpetuate␈αitself.
␈β∪(

␈β↓Y␈↓ ↓H␈εα4␈↓ α=␈ε∞RA␈α␈NDOM␈α	NUMBERS␈εα␈↓ 
}3.1
␈βα(␈↓ α␈εαSev␈α␈eral␈α⊂people␈α⊃experimen␈α␈ted␈α⊂with␈α⊂the␈α⊂middle-square␈α⊃method␈α⊂in␈α⊂the␈α⊂early
␈βαS␈↓ ↓H␈εα1950s.␈αWorking␈αwith␈αfour-digit␈α
n␈α␈um␈α␈bers␈αinstead␈αof␈α
10-digit␈αones,␈αG.␈αE.␈α
Forsythe
␈βα}␈↓ ↓H␈εαtried␈απ16␈απdi{eren␈α␈t␈απstarting␈απvalues␈απand␈απfound␈αλthat␈απ12␈απof␈απthem␈απled␈απto␈απsequences␈απending
␈ββ*␈↓ ↓H␈εαwith␈αλthe␈αλcy␈α␈cle␈αλ6100,␈α	2100,␈α	4100,␈α	8100,␈α	6100,␈↓ εl␈εα.␈αε.␈αε.␈↓ π≤␈εα,␈α	while␈α	t␈α␈w␈α␈o␈αλof␈αλthem␈αλdegenerated␈αλto
␈ββU␈↓ ↓H␈εαzero.␈αN.␈α
Metropolis␈αalso␈α
conducted␈α
extensiv␈α␈e␈α
tests␈αon␈α
the␈α
middle-square␈α
method,
␈β∧␈↓ ↓H␈εαmostly␈αin␈α
the␈α
binary␈α
n␈α␈um␈α␈ber␈αsystem.␈α∂He␈α
sho␈α␈w␈α␈ed␈αthat␈α
when␈α
20-bit␈α
n␈α␈um␈α␈bers␈αare
␈β∧+␈↓ ↓H␈εαbeing␈απused,␈α	there␈αλare␈αλ13␈αλdi{eren␈α␈t␈απcy␈α␈cles␈αλin␈α␈to␈αλwhich␈αλthe␈αλsequence␈αλmigh␈α␈t␈απdegenerate,
␈β∧V␈↓ ↓H␈εαthe␈αlongest␈αof␈αwhich␈αhas␈αa␈αperiod␈αof␈αlength␈α142.
␈β¬ε␈↓ α␈εαIt␈α∞is␈α
fairly␈α∞easy␈α
to␈α∞restart␈α
the␈α∞middle-square␈α∞method␈α
on␈α∞a␈α
new␈α∞value␈α
when
␈β¬1␈↓ ↓H␈εαzero␈α
has␈α
been␈α
detected,␈α
but␈α
long␈α
cy␈α␈cles␈α
are␈α
somewhat␈α
harder␈α
to␈α
av␈α␈oid.␈αEx␈α␈ercise␈α
7
␈β¬\␈↓ ↓H␈εαdiscusses␈α∂some␈α∂in␈α␈teresting␈α∂ways␈α∂to␈α∂determine␈α∂the␈α∂cy␈α␈cles␈α∂of␈α∂periodic␈α∂sequences,
␈βελ␈↓ ↓H␈εαusing␈αv␈α␈ery␈αlittle␈αmemory␈αspace.
␈βε7␈↓ α␈εαA␈α
theoretical␈α
disadvan␈α␈tage␈α
of␈α
the␈α
middle-square␈α
method␈α
is␈α
giv␈α␈en␈α
in␈α	ex␈α␈ercises
␈βεb␈↓ ↓H␈εα9␈αλand␈α	10.␈α
On␈α	the␈αλother␈α	hand,␈α	w␈α␈orking␈αλwith␈α	38-bit␈αλn␈α␈um␈α␈bers,␈α
Metropolis␈αλobtained␈αλa
␈βπ∞␈↓ ↓H␈εαsequence␈αλof␈α	about␈α	750,000␈α	n␈α␈um␈α␈bers␈α	before␈α	degeneracy␈αλoccurred,␈α
and␈α	the␈αλresulting
␈βπ9␈↓ ↓H␈εα750,000␈ε⊗␈ααα␈εα␈αα38␈αλbits␈αλsatisfactorily␈αλpassed␈αλstatistical␈απtests␈αλfor␈αλrandomness.␈αThis␈απsho␈α␈ws
␈βπd␈↓ ↓H␈εαthat␈α	the␈α
middle-square␈α
method␈ε∂␈α
can␈εα␈α
giv␈α␈e␈α	usable␈α
results,␈α
but␈α
it␈α
is␈α
rather␈α	dangerous
␈βλ∂␈↓ ↓H␈εαto␈αput␈αm␈α␈uch␈αfaith␈αin␈αit␈αun␈α␈til␈αafter␈αelaborate␈αcomputations␈αhav␈α␈e␈αbeen␈αperformed.
␈βλW␈↓ α␈εαMan␈α␈y␈α
random-n␈α␈um␈α␈ber␈α
generators␈α
in␈α
use␈α
today␈α
are␈α
not␈α
v␈α␈ery␈α
good.␈α∞There␈α
is
␈β	α␈↓ ↓H␈εαa␈αtendency␈α
for␈αpeople␈α
to␈α
av␈α␈oid␈αlearning␈α
an␈α␈ything␈αabout␈α
such␈α
subroutines;␈αquite
␈β	-␈↓ ↓H␈εαoften␈α⊂w␈α␈e␈α∂|nd␈α⊂that␈α⊂some␈α⊂old␈α⊂method␈α⊂that␈α⊂is␈α⊂comparativ␈α␈ely␈α⊂unsatisfactory␈α∂has
␈β	X␈↓ ↓H␈εαblindly␈α∞been␈α∞passed␈α
do␈α␈wn␈α∞from␈α∞one␈α∞programmer␈α∞to␈α∞another,␈α∂and␈α∞today's␈α
users
␈β
β␈↓ ↓H␈εαhav␈α␈e␈α
no␈αunderstanding␈α
of␈α
its␈α
limitations.␈α∂We␈αshall␈α
see␈α
in␈α
this␈α
chapter␈α
that␈α
it␈αis
␈β
/␈↓ ↓H␈εαnot␈αdi}cult␈αto␈αlearn␈αthe␈αmost␈αimportan␈α␈t␈αfacts␈αabout␈αrandom-n␈α␈um␈α␈ber␈αgenerators
␈β
Z␈↓ ↓H␈εαand␈αtheir␈αproper␈αuse.
␈β	␈↓ α␈εαIt␈αis␈αnot␈αeasy␈αto␈α
in␈α␈v␈α␈en␈α␈t␈αa␈αfoolproof␈αrandom-n␈α␈um␈α␈ber␈αgenerator.␈αThis␈αfact␈α
was
␈β5␈↓ ↓H␈εαcon␈α␈vincingly␈α
impressed␈α∞upon␈α∞the␈α∞author␈α
sev␈α␈eral␈α∞y␈α␈ears␈α∞ago,␈α∞when␈α∞he␈α
attempted
␈β`␈↓ ↓H␈εαto␈αcreate␈αa␈αfan␈α␈tastically␈αgood␈αone␈αusing␈αthe␈αfollo␈α␈wing␈αpeculiar␈αapproach:
␈β?␈↓ ↓H␈ε∩Algorithm␈α⊃K␈εα␈α⊃(␈ε∂\Super-random"␈α⊃n␈α␈um␈α␈ber␈α⊃generator␈↓ πb␈εα)␈ε∩.␈εα␈α"Giv␈α␈en␈α⊃a␈α⊃10-digit␈α⊃decimal
␈βj␈↓ ↓H␈εαn␈α␈um␈α␈ber␈↓ αJ␈ελX␈↓ αh␈εα,␈αthis␈α
algorithm␈αmay␈αbe␈α
used␈αto␈αchange␈↓ πa␈ελX␈↓ λ␈εαto␈αthe␈α
n␈α␈um␈α␈ber␈αthat␈αshould
␈β
⊗␈↓ ↓H␈εαcome␈αnext␈α
in␈α
a␈α
supposedly␈αrandom␈α
sequence.␈α∞Although␈α
the␈α
algorithm␈α
migh␈α␈t␈αbe
␈β
A␈↓ ↓H␈εαexpected␈αto␈αyield␈αquite␈αa␈αrandom␈αsequence,␈α
reasons␈αgiv␈α␈en␈αbelo␈α␈w␈αsho␈α␈w␈αthat␈αit␈αis,
␈β
l␈↓ ↓H␈εαin␈α
fact,␈αnot␈αv␈α␈ery␈αgood␈αat␈αall.␈α⊗(The␈αreader␈αneed␈α
not␈αstudy␈αthis␈αalgorithm␈αin␈α
great
␈β∞↔␈↓ ↓H␈εαdetail␈αex␈α␈cept␈αto␈αobserv␈α␈e␈αits␈αcomplexity;␈αnote,␈αin␈αparticular,␈αsteps␈αK1␈αand␈αK2.)
␈β∞Y␈↓ πl␈ε¬9
␈β∞←␈↓ ↓H␈ε∩K1.␈↓ α␈εα[Choose␈αn␈α␈um␈α␈ber␈α
of␈αiterations.]␈α⊗Set␈↓ ε7␈ελY␈↓ ε\␈ε⊗ ␈α
b␈↓ π_␈ελX␈↓ π6␈εα/1␈↓ πZ␈εα0␈↓ πz␈ε⊗c␈εα␈α,␈α
the␈αmost␈αsigni|can␈α␈t␈α
digit
␈β∂
␈↓ α␈εαof␈↓ α6␈ελX␈↓ αS␈εα.␈α_(We␈αwill␈αex␈α␈ecute␈αsteps␈αK2␈αthrough␈αK13␈αexactly␈↓ λh␈ελY␈↓ 	␈εα+␈απ1␈αtimes;␈αthat␈αis,
␈β∂5␈↓ α␈εαw␈α␈e␈αwill␈αapply␈αrandomizing␈αtransformations␈αa␈ε∂␈αrandom␈εα␈αn␈α␈um␈α␈ber␈αof␈αtimes.)
␈β∂w␈↓ εh␈ε¬8
␈β∂|␈↓ ↓H␈ε∩K2.␈↓ α␈εα[Choose␈α	random␈α
step.]␈α∩Set␈↓ ¬4␈ελZ␈↓ ¬X␈ε⊗ ␈α
b␈↓ ε∀␈ελX␈↓ ε2␈εα/1␈↓ εV␈εα0␈↓ εv␈ε⊗c␈↓ π
␈εαmod␈↓ πT␈εα10,␈α
the␈α	second␈α	most␈α	signi|can␈α␈t
␈β⊂(␈↓ α␈εαdigit␈αof␈↓ β␈ελX␈↓ β)␈εα.␈α
Go␈αto␈αstep␈αK(3␈α	+␈↓ ¬a␈ελZ␈↓ ¬z␈εα).␈α~(That␈αis,␈α
w␈α␈e␈αno␈α␈w␈αjump␈α
to␈αa␈ε∂␈αrandom␈εα␈αstep
␈β⊂S␈↓ α␈εαin␈αthe␈αprogram.)
␈β⊃∃␈↓ ∧&␈ε¬9
␈β⊃~␈↓ ↓H␈ε∩K3.␈↓ α␈εα[Ensure␈ε⊗␈α∃␈εα␈α
5␈ε⊗␈αλα␈εα␈αλ1␈↓ ∧∀␈εα0␈↓ ∧4␈εα.]␈α~If␈↓ ¬ε␈ελX␈↓ ¬.␈εα<␈α
5000000000,␈αset␈↓ π↑␈ελX␈↓ λε␈ε⊗ ␈↓ λ4␈ελX␈↓ λY␈εα+␈αλ5000000000.
␈β∪(

␈β↓Y␈↓ ↓H␈εα3.1␈ε∞␈↓ λYINTR␈α␈ODUCT␈α␈ION␈↓ ~␈εα5
␈βα!␈↓ ε&␈ε¬2␈↓ εj␈ε¬5␈↓ π{␈ε¬10
␈βα&␈↓ ↓H␈ε∩K4.␈↓ α␈εα[Middle␈α
square.]␈α⊗Replace␈↓ ¬∨␈ελX␈↓ ¬H␈εαby␈ε⊗␈α
b␈↓ ελ␈ελX␈↓ ε4␈εα/1␈↓ εX␈εα0␈↓ εy␈ε⊗c␈↓ π
␈εαmod␈↓ πW␈εα1␈↓ πi␈εα0␈↓ λ↔␈εα,␈αi.e.,␈αby␈α
the␈αmiddle␈α
of␈α
the
␈βαQ␈↓ α␈εαsquare␈αof␈↓ β&␈ελX␈↓ βD␈εα.
␈ββ
␈↓ λ∀␈ε¬1␈α↓0
␈ββ∪␈↓ ↓H␈ε∩K5.␈↓ α␈εα[Multiply.]␈α→Replace␈↓ ∧R␈ελX␈↓ ∧|␈εαby␈α(1001001001␈↓ εv␈ελX␈↓ π∀␈εα)␈↓ π&␈εαmod␈↓ πp␈εα1␈↓ λα␈εα0␈↓ λ1␈εα.
␈ββT␈↓ ↓H␈ε∩K6.␈↓ α␈εα[Pseudo-complemen␈α␈t.]␈α≠If␈↓ ¬!␈ελX␈↓ ¬K␈εα<␈α100000000,␈α∞then␈α
set␈↓ λA␈ελX␈↓ λk␈ε⊗ ␈↓ 	≠␈ελX␈↓ 	B␈εα+␈αλ9814055677;
␈ββz␈↓ ∧↑␈ε¬10
␈ββ␈␈↓ α␈εαotherwise␈αset␈↓ βd␈ελX␈↓ ∧␈ε⊗ ␈εα␈α
1␈↓ ∧L␈εα0␈↓ ¬β␈ε⊗␈␈↓ ¬/␈ελX␈↓ ¬M␈εα.
␈β∧@␈↓ ↓H␈ε∩K7.␈↓ α␈εα[In␈α␈terchange␈α⊂halv␈α␈es.]␈α In␈α␈terchange␈α∂the␈α⊂lo␈α␈w-order␈α⊂|v␈α␈e␈α⊂digits␈α∂of␈↓ 	w␈ελX␈↓ 
%␈εαwith␈α∂the
␈β∧f␈↓ ε:␈ε¬5␈↓ πf␈ε¬5␈↓ 	~␈ε¬5
␈β∧k␈↓ α␈εαhigh-order␈α∞|v␈α␈e␈α∂digits,␈α∂i.e.,␈↓ ¬8␈ελX␈↓ ¬d␈ε⊗ ␈εα␈α∞1␈↓ ε(␈εα0␈↓ εI␈εα(␈↓ εU␈ελX␈↓ εx␈εαmod␈↓ πB␈εα1␈↓ πT␈εα0␈↓ πu␈εα)␈α
+␈ε⊗␈α	b␈↓ λF␈ελX␈↓ λd␈εα/1␈↓ 	λ␈εα0␈↓ 	(␈ε⊗c␈εα,␈α⊂the␈α∞middle␈α∞10
␈β¬⊃␈↓ βH␈ε¬10
␈β¬⊗␈↓ α␈εαdigits␈αof␈α(1␈↓ β6␈εα0␈↓ βm␈εα+␈αλ1)␈↓ ∧7␈ελX␈↓ ∧U␈εα.
␈β¬W␈↓ ↓H␈ε∩K8.␈↓ α␈εα[Multiply.]␈α→Same␈αas␈αstep␈αK5.
␈βε_␈↓ ↓H␈ε∩K9.␈↓ α␈εα[Decrease␈αdigits.]␈α∃Decrease␈αeach␈α
nonzero␈αdigit␈α
of␈α
the␈αdecimal␈α
represen␈α␈tation
␈βεD␈↓ α␈εαof␈↓ α6␈ελX␈↓ α`␈εαby␈αone.
␈βπ␈↓ ¬S␈ε¬5␈↓ π;␈ε¬2
␈βπ¬␈↓ ↓6␈ε∩K10.␈↓ α␈εα[99999␈α⊂modify.]␈α!If␈↓ ∧K␈ελX␈↓ ∧z␈εα<␈α⊃1␈↓ ¬A␈εα0␈↓ ¬b␈εα,␈α⊃set␈↓ ε9␈ελX␈↓ εh␈ε⊗ ␈↓ π≥␈ελX␈↓ πT␈εα+␈α99999;␈α∩otherwise␈α⊂set␈↓ 
Z␈ελX␈↓ λ␈ε⊗ 
␈βπ0␈↓ α␈ελX␈↓ α2␈ε⊗␈␈εα␈αλ99999.
␈βπl␈↓ 	2␈ε¬9
␈βπq␈↓ ↓6␈ε∩K11.␈↓ α␈εα[Normalize.]␈α≠(At␈α
this␈α
poin␈α␈t␈↓ ¬K␈ελX␈↓ ¬v␈εαcannot␈α
be␈α∞zero.)␈α≠If␈↓ λ5␈ελX␈↓ λ↑␈εα<␈α1␈↓ 	 ␈εα0␈↓ 	A␈εα,␈α
set␈↓ 
⊃␈ελX␈↓ 
;␈ε⊗ ␈εα␈α10␈↓ ∞␈ελX
␈βλ≤␈↓ α␈εαand␈αrepeat␈αthis␈αstep.
␈βλX␈↓ λ{␈ε¬5␈↓ 
␈ε¬1␈α↓0
␈βλ]␈↓ ↓6␈ε∩K12.␈↓ α␈εα[Modi|ed␈α
middle␈α
square.]␈α≠Replace␈↓ ε<␈ελX␈↓ εg␈εαby␈ε⊗␈α
b␈↓ π*␈ελX␈↓ πH␈εα(␈↓ πT␈ελX␈↓ π{␈ε⊗␈␈εα␈αλ1)/1␈↓ λi␈εα0␈↓ 		␈ε⊗c␈↓ 	≥␈εαmod␈↓ 	g␈εα1␈↓ 	y␈εα0␈↓ 
(␈εα,␈α
i.e.,␈α
by
␈β		␈↓ α␈εαthe␈αmiddle␈α10␈αdigits␈αof␈↓ ∧|␈ελX␈↓ ¬~␈εα(␈↓ ¬&␈ελX␈↓ ¬L␈ε⊗␈␈εα␈αλ1).
␈β	J␈↓ ↓6␈ε∩K13.␈↓ α␈εα[Repeat?]␈α~If␈↓ β\␈ελY␈↓ ∧α␈εα>␈α0,␈α
decrease␈↓ ¬i␈ελY␈↓ ε⊂␈εαby␈α
1␈αand␈α
return␈α
to␈αstep␈α
K2.␈α∞If␈↓ 	⎇␈ελY␈↓ 
#␈εα=␈α0,␈αthe
␈β	u␈↓ α␈εαalgorithm␈αterminates␈αwith␈↓ ¬4␈ελX␈↓ ¬↑␈εαas␈αthe␈αdesired␈α\random"␈αvalue.
␈β	z␈↓ 	e␈∧	z	e≠∂
␈β
I␈↓ α␈εα(The␈αmachine-language␈α
program␈αcorresponding␈αto␈α
the␈αabo␈α␈v␈α␈e␈αalgorithm␈αwas
␈β
t␈↓ ↓H␈εαin␈α␈tended␈α
to␈α∞be␈α
so␈α∞complicated␈α
that␈α∞a␈α∞person␈α
reading␈α∞a␈α
listing␈α∞of␈α
it␈α∞without␈α
ex-
␈β∨␈↓ ↓H␈εαplanatory␈αcommen␈α␈ts␈αw␈α␈ouldn't␈αkno␈α␈w␈αwhat␈αthe␈αprogram␈αwas␈αdoing.)
␈βM␈↓ α␈εαConsidering␈α∂all␈α⊂the␈α∂con␈α␈tortions␈α⊂of␈α∂Algorithm␈α⊂K␈↓ λε␈εα,␈α⊂doesn't␈α⊂it␈α∂seem␈α∂plausible
␈βy␈↓ ↓H␈εαthat␈α
it␈α∞should␈α∞produce␈α
almost␈α∞an␈α∞in|nite␈α∞supply␈α
of␈α∞un␈α␈believably␈α∞random␈α
n␈α␈um-
␈β$␈↓ ↓H␈εαbers?␈α
No!␈α∞In␈αfact,␈α
when␈α
this␈αalgorithm␈α
was␈α|rst␈α
put␈αon␈α␈to␈α
a␈αcomputer,␈α
it␈αalmost
␈βO␈↓ ↓H␈εαimmediately␈αcon␈α␈v␈α␈erged␈α
to␈α
the␈α
10-digit␈α
value␈α
6065038420,␈α
which←by␈αextraordi-
␈βz␈↓ ↓H␈εαnary␈α	coincidence←is␈α
transformed␈α	in␈α␈to␈α	itself␈α
by␈α	the␈α
algorithm␈α	(see␈α
Table␈α	1).␈αWith
␈β
%␈↓ ↓H␈εαanother␈α∞starting␈α∞n␈α␈um␈α␈ber,␈α∂the␈α∞sequence␈α∂began␈α∞to␈α∞repeat␈α∂after␈α∞7401␈α∞values,␈α∂in␈α∞a
␈β
Q␈↓ ↓H␈εαcy␈α␈clic␈αperiod␈αof␈αlength␈α3178.
␈β
␈␈↓ α␈εαThe␈α∂moral␈α∂of␈α∂this␈α∂story␈α∂is␈α∂that␈ε∂␈α∂random␈α∂n␈α␈um␈α␈bers␈α∂should␈α∂not␈α∂be␈α∂generated
␈β∞*␈↓ ↓H␈ε∂with␈αa␈αmethod␈αchosen␈αat␈αrandom.␈εα␈αSome␈αtheory␈αshould␈αbe␈αused.
␈β∞k␈↓ α␈εαIn␈απthis␈αλchapter,␈αλw␈α␈e␈απshall␈απconsider␈απrandom-n␈α␈um␈α␈ber␈αλgenerators␈απthat␈απare␈απsuperior
␈β∂⊗␈↓ ↓H␈εαto␈αthe␈α
middle-square␈α
method␈α
and␈α
to␈α
Algorithm␈α
K␈↓ πZ␈εα;␈α
the␈α
corresponding␈αsequences
␈β∂A␈↓ ↓H␈εαare␈αguaran␈α␈teed␈α
to␈αhav␈α␈e␈α
certain␈αdesirable␈αrandom␈α
properties,␈α
and␈αno␈αdegeneracy
␈β∂l␈↓ ↓H␈εαwill␈α
occur.␈αWe␈α
shall␈α
explore␈αthe␈α
reasons␈αfor␈α
this␈αrandom␈α
behavior␈αin␈α
some␈α
detail,
␈β⊂_␈↓ ↓H␈εαand␈α∂w␈α␈e␈α∂shall␈α⊂also␈α∂consider␈α∂techniques␈α⊂for␈α∂manipulating␈α∂random␈α∂n␈α␈um␈α␈bers.␈α⊗For
␈β⊂C␈↓ ↓H␈εαexample,␈α∂one␈α∞of␈α∂our␈α∞in␈α␈v␈α␈estigations␈α∂will␈α∞be␈α∂the␈α∞sh␈α␈u␈␈ing␈α∂of␈α∞a␈α∞sim␈α␈ulated␈α∂deck␈α∞of
␈β⊂n␈↓ ↓H␈εαcards␈αwithin␈αa␈αcomputer␈αprogram.
␈β⊃≤␈↓ α␈εαSection␈απ3.6␈απsummarizes␈απthis␈απchapter␈απand␈απlists␈απimportan␈α␈t␈απbibliographic␈απsources.
␈β∪(

␈β↓Y␈↓ ↓H␈εα6␈↓ α=␈ε∞RA␈α␈NDOM␈α	NUMBERS␈εα␈↓ 
}3.1
␈βα≥␈↓ ¬{␈ε≥Ta␈α␈b␈α↓le␈α
1
␈βαH␈↓ αv␈εβA␈αCOL␈α␈OS␈α␈SAL␈αCOINCIDENCE:␈αTH␈α↓E␈αNUM␈α␈B␈α↓ER␈α60␈α␈65␈α␈038␈α␈420
␈βαo␈↓ β
␈εβI␈α↓S␈α
TRANSF␈α␈ORM␈α␈E␈α↓D␈αINTO␈αITS␈α␈E␈α↓LF␈αBY␈αALGORITHM␈α
K.
␈ββ∃␈↓ ↓H␈∧β∃↓Hα	e
␈ββ⊗␈↓ ε9␈∧β⊗ε9π↑α
␈ββ-␈↓ α≥␈εβS␈α␈tep␈↓ β8␈ε	X␈↓ β←␈εβ(afte␈α␈r)␈↓ πβ␈εβS␈α␈tep␈↓ λ≡␈ε	X␈↓ λE␈εβ(a␈α␈f␈α↓te␈α␈r)
␈ββ←␈↓ πβ␈εβK9␈↓ λ␈εβ1␈α␈10␈α␈785␈α␈570␈α␈0
␈ββs␈↓ α≥␈εβK1␈↓ β&␈εβ6␈α␈065␈α␈038␈α␈42␈α␈0
␈β∧π␈↓ πβ␈εβK1␈α␈0␈↓ λ␈εβ1␈α␈10␈α␈775␈α␈570␈α␈1
␈β∧≠␈↓ α≥␈εβK3␈↓ β&␈εβ6␈α␈065␈α␈038␈α␈42␈α␈0
␈β∧/␈↓ πβ␈εβK1␈α␈1␈↓ λ␈εβ1␈α␈10␈α␈775␈α␈570␈α␈1
␈β∧B␈↓ α≥␈εβK4␈↓ β&␈εβ6␈α␈910␈α␈360␈α␈76␈α␈0
␈β∧V␈↓ πβ␈εβK1␈α␈2␈↓ λ␈εβ1␈α␈22␈α␈691␈α␈990␈α␈2␈↓ 	z␈ε	Y␈↓ 
≤␈εβ=␈α
3
␈β∧j␈↓ α≥␈εβK5␈↓ β&␈εβ8␈α␈031␈α␈120␈α␈76␈α␈0
␈β∧}␈↓ πβ␈εβK5␈↓ λ␈εβ0␈α␈04␈α␈882␈α␈190␈α␈2
␈β¬∩␈↓ α≥␈εβK6␈↓ β&␈εβ1␈α␈968␈α␈879␈α␈24␈α␈0
␈β¬%␈↓ πβ␈εβK6␈↓ λ␈εβ9␈α␈86␈α␈287␈α␈757␈α␈9
␈β¬9␈↓ α≥␈εβK7␈↓ β&␈εβ7␈α␈924␈α␈019␈α␈68␈α␈8
␈β¬M␈↓ πβ␈εβK7␈↓ λ␈εβ7␈α␈75␈α␈799␈α␈862␈α␈8
␈β¬a␈↓ α≥␈εβK8␈↓ β&␈εβ9␈α␈631␈α␈707␈α␈68␈α␈8
␈β¬u␈↓ πβ␈εβK8␈↓ λ␈εβ2␈α␈38␈α␈462␈α␈662␈α␈8
␈βελ␈↓ α≥␈εβK9␈↓ β&␈εβ8␈α␈520␈α␈606␈α␈57␈α␈7
␈βε≤␈↓ πβ␈εβK9␈↓ λ␈εβ1␈α␈27␈α␈351␈α␈551␈α␈7
␈βε0␈↓ α≥␈εβK1␈α␈0␈↓ β&␈εβ8␈α␈520␈α␈506␈α␈57␈α␈8
␈βεD␈↓ πβ␈εβK1␈α␈0␈↓ λ␈εβ1␈α␈27␈α␈341␈α␈551␈α␈8
␈βεX␈↓ α≥␈εβK1␈α␈1␈↓ β&␈εβ8␈α␈520␈α␈506␈α␈57␈α␈8
␈βεk␈↓ πβ␈εβK1␈α␈1␈↓ λ␈εβ1␈α␈27␈α␈341␈α␈551␈α␈8
␈βε␈␈↓ α≥␈εβK1␈α␈2␈↓ β&␈εβ0␈α␈323␈α␈372␈α␈20␈α␈7␈↓ ¬∀␈ε	Y␈↓ ¬6␈εβ=␈α
6
␈βπ∪␈↓ πβ␈εβK1␈α␈2␈↓ λ␈εβ5␈α␈87␈α␈080␈α␈209␈α␈7␈↓ 	z␈ε	Y␈↓ 
≤␈εβ=␈α
2
␈βπ'␈↓ α≥␈εβK6␈↓ β&␈εβ9␈α␈676␈α␈627␈α␈79␈α␈3
␈βπ;␈↓ πβ␈εβK1␈α␈1␈↓ λ␈εβ5␈α␈87␈α␈080␈α␈209␈α␈7
␈βπN␈↓ α≥␈εβK7␈↓ β&␈εβ2␈α␈779␈α␈396␈α␈76␈α␈6
␈βπb␈↓ πβ␈εβK1␈α␈2␈↓ λ␈εβ3␈α␈17␈α␈256␈α␈268␈α␈7␈↓ 	z␈ε	Y␈↓ 
≤␈εβ=␈α
1
␈βπv␈↓ α≥␈εβK8␈↓ β&␈εβ4␈α␈942␈α␈162␈α␈76␈α␈6
␈βλ
␈↓ πβ␈εβK4␈↓ λ␈εβ1␈α␈54␈α␈002␈α␈944␈α␈6
␈βλ≡␈↓ α≥␈εβK9␈↓ β&␈εβ3␈α␈831␈α␈051␈α␈65␈α␈5
␈βλ1␈↓ πβ␈εβK5␈↓ λ␈εβ7␈α␈01␈α␈547␈α␈544␈α␈6
␈βλE␈↓ α≥␈εβK1␈α␈0␈↓ β&␈εβ3␈α␈830␈α␈951␈α␈65␈α␈6
␈βλY␈↓ πβ␈εβK6␈↓ λ␈εβ2␈α␈98␈α␈452␈α␈455␈α␈4
␈βλm␈↓ α≥␈εβK1␈α␈1␈↓ β&␈εβ3␈α␈830␈α␈951␈α␈65␈α␈6
␈β	↓␈↓ πβ␈εβK7␈↓ λ␈εβ2␈α␈45␈α␈542␈α␈984␈α␈5
␈β	∀␈↓ α≥␈εβK1␈α␈2␈↓ β&␈εβ1␈α␈905␈α␈867␈α␈78␈α␈1␈↓ ¬∀␈ε	Y␈↓ ¬6␈εβ=␈α
5
␈β	(␈↓ πβ␈εβK8␈↓ λ␈εβ2␈α␈73␈α␈027␈α␈484␈α␈5
␈β	<␈↓ α≥␈εβK1␈α␈2␈↓ β&␈εβ3␈α␈319␈α␈967␈α␈47␈α␈9␈↓ ¬∀␈ε	Y␈↓ ¬6␈εβ=␈α
4
␈β	P␈↓ πβ␈εβK9␈↓ λ␈εβ1␈α␈62␈α␈016␈α␈373␈α␈4
␈β	d␈↓ α≥␈εβK6␈↓ β&␈εβ6␈α␈680␈α␈032␈α␈52␈α␈1
␈β	w␈↓ πβ␈εβK1␈α␈0␈↓ λ␈εβ1␈α␈62␈α␈006␈α␈373␈α␈5
␈β
␈↓ α≥␈εβK7␈↓ β&␈εβ3␈α␈252␈α␈166␈α␈80␈α␈0
␈β
∨␈↓ πβ␈εβK1␈α␈1␈↓ λ␈εβ1␈α␈62␈α␈006␈α␈373␈α␈5
␈β
3␈↓ α≥␈εβK8␈↓ β&␈εβ2␈α␈218␈α␈966␈α␈80␈α␈0
␈β
G␈↓ πβ␈εβK1␈α␈2␈↓ λ␈εβ6␈α␈06␈α␈503␈α␈842␈α␈0␈↓ 	z␈ε	Y␈↓ 
≤␈εβ=␈α
0
␈β
s␈↓ ↓H␈∧
s↓Hα	e
␈βI␈↓ ↓H␈ε≥E␈α␈XERCI␈α↓SE␈α␈S
␈β⊗␈↓ ↓;␈ε↓x
␈β~␈↓ ↓g␈ε∪1.␈↓ α␈εβ[␈ε	20␈↓ α;␈εβ]␈α⊗Su␈α␈pp␈α␈ose␈α∂th␈α␈at␈α⊂y␈α}ou␈α∂wish␈α∂to␈α∂ob␈α␈tain␈α∂a␈α∂dec␈α␈i␈α↓m␈α␈al␈α⊂d␈α␈i␈α↓g␈α␈it␈α⊂at␈α∂ran␈α␈do␈α␈m,␈α⊃n␈α␈ot␈α∂using␈α∂a
␈βB␈↓ ↓H␈εβc␈α␈omp␈α␈uter.␈αWhich␈α
of␈αthe␈αfo␈α␈l␈α↓lo␈α␈win␈α␈g␈αmeth␈α␈od␈α␈s␈αw␈α␈ould␈α
be␈αsu␈α␈itable?
␈βt␈↓ ↓e␈εβa)␈↓ α␈εβOp␈α␈en␈αεa␈αεteleph␈α␈on␈α␈e␈απd␈α␈irectory␈αεt␈α␈o␈απa␈αεra␈α␈nd␈α␈om␈αεplac␈α␈e␈απ(i.e.,␈αλstick␈αεy␈α␈o␈α␈ur␈αε|n␈α␈ger␈αεin␈αεi␈α↓t␈αεsom␈α␈ewhere␈α␈)
␈β
≠␈↓ α␈εβan␈α␈d␈αu␈α␈se␈αthe␈α
un␈α␈i␈α↓ts␈αd␈α␈igit␈αof␈αthe␈α|␈α␈rst␈αn␈α␈u␈α␈m␈α␈b␈α␈er␈αfoun␈α␈d␈αo␈α␈n␈αth␈α␈e␈αselected␈α
pa␈α␈ge.
␈β
C␈↓ ↓c␈εβb)␈↓ α␈εβSa␈α␈me␈αa␈α␈s␈α(a␈α␈),␈αb␈α␈ut␈αu␈α␈se␈αthe␈α
un␈α␈i␈α↓ts␈αd␈α␈igit␈αof␈αthe␈ε⊂␈αp␈α␈ag␈α␈e␈εβ␈αn␈α␈u␈α␈m␈α␈ber␈α␈.
␈β
k␈↓ ↓g␈εβc)␈↓ α␈εβRoll␈αa␈αdie␈αth␈α␈at␈αis␈αin␈αthe␈αsha␈α␈pe␈αof␈αa␈αregu␈α␈l␈α↓a␈α␈r␈αicosa␈α␈he␈α␈dron␈α␈,␈αwhos␈α␈e␈αt␈α␈w␈α␈en␈α␈ty␈αfac␈α␈es␈αh␈α␈av␈α␈e
␈β∞∩␈↓ α␈εβbe␈α␈en␈αlabe␈α␈l␈α↓e␈α␈d␈α
with␈αth␈α␈e␈α
d␈α␈igits␈α
0,␈α¬0,␈αε1␈α␈,␈αε1,␈↓ ε0␈εβ.␈α¬.␈αε.␈↓ ε\␈εβ,␈αε9,␈α¬9.␈α⊂Use␈αthe␈αd␈α␈i␈α↓g␈α␈i␈α↓t␈αtha␈α␈t␈α
a␈α␈pp␈α␈ears␈αon␈αtop␈α␈,
␈β∞:␈↓ α␈εβwhe␈α␈n␈αt␈α␈he␈α
die␈αc␈α␈omes␈α
to␈α
rest.␈α_(A␈αfelt␈αta␈α␈ble␈α
wi␈α↓th␈α
a␈α
h␈α␈ard␈α
surfa␈α␈ce␈αis␈α
recom␈α␈men␈α␈ded␈α
fo␈α␈r
␈β∞a␈↓ α␈εβrolling␈αd␈α␈ice.)
␈β∂	␈↓ ↓c␈εβd)␈↓ α␈εβExp␈α␈ose␈αλa␈α	g␈α␈eiger␈αλcou␈α␈n␈α␈ter␈αλto␈αλa␈α	so␈α␈urce␈αλof␈αλrad␈α␈i␈α↓o␈α␈activity␈αλfor␈αλon␈α␈e␈α	min␈α}ute␈αλ(shieldin␈α␈g␈α	y␈α}ou␈α␈r-
␈β∂1␈↓ α␈εβself)␈α
an␈α␈d␈α
u␈α␈se␈α
th␈α␈e␈α
u␈α␈nits␈α
d␈α␈i␈α↓g␈α␈i␈α↓t␈α	of␈α
the␈α	resu␈α␈l␈α↓tin␈α␈g␈α
co␈α␈un␈α}t.␈αAssum␈α␈e␈α
tha␈α␈t␈α
the␈α	geige␈α␈r␈α
cou␈α␈n␈α␈te␈α␈r
␈β∂X␈↓ α␈εβdisp␈α␈lays␈αth␈α␈e␈αn␈α␈u␈α␈m␈α␈be␈α␈r␈αof␈αcou␈α␈n␈α␈ts␈αin␈αd␈α␈ecima␈α␈l␈αn␈α␈otatio␈α␈n,␈αan␈α␈d␈αtha␈α␈t␈αthe␈αc␈α␈oun␈α}t␈αi␈α↓s␈αin␈α␈i␈α↓tia␈α␈l␈α↓ly
␈β⊂␈↓ α␈εβzero␈α␈.
␈β⊂'␈↓ ↓g␈εβe)␈↓ α␈εβGlan␈α␈ce␈αat␈αy␈α}ou␈α␈r␈α
wrist␈α␈wa␈α␈tch;␈α
a␈α␈nd␈αi␈α↓f␈αth␈α␈e␈αpo␈α␈si␈α↓t␈α␈i␈α↓o␈α␈n␈αof␈αth␈α␈e␈αseco␈α␈nd␈α␈-␈α↓h␈α␈an␈α␈d␈αis␈αbe␈α␈t␈α␈we␈α␈en␈α6␈↓ _␈ε	n
␈β⊂O␈↓ α␈εβan␈α␈d␈α6␈α␈(␈↓ αi␈ε	n␈↓ β∧␈εβ+␈αλ1␈α␈)␈αs␈α␈econ␈α␈ds,␈αch␈α␈oose␈α
the␈αd␈α␈i␈α↓g␈α␈it␈↓ εF␈ε	n␈↓ εZ␈εβ.
␈β⊂w␈↓ ↓k␈εβf)␈↓ α␈εβAsk␈αa␈α
fri␈α↓e␈α␈nd␈αto␈α
thin␈α␈k␈αof␈αa␈αra␈α␈nd␈α␈om␈αd␈α␈i␈α↓g␈α␈it,␈αa␈α␈nd␈α
use␈αth␈α␈e␈αdigit␈αh␈α␈e␈αna␈α␈mes.
␈β⊃≡␈↓ ↓e␈εβg)␈↓ α␈εβAsk␈αa␈α␈n␈αen␈α␈em␈α␈y␈α
to␈αthin␈α␈k␈αof␈αa␈αr␈α␈and␈α␈om␈αd␈α␈igit,␈αa␈α␈nd␈α
use␈αth␈α␈e␈αdig␈α␈i␈α↓t␈αh␈α␈e␈αna␈α␈mes.
␈β∪(

␈β↓Y␈↓ ↓H␈εα3.1␈ε∞␈↓ λYINTR␈α␈ODUCT␈α␈ION␈↓ ~␈εα7
␈βα*␈↓ ↓c␈εβh)␈↓ α␈εβAssu␈α␈me␈αth␈α␈at␈α
10␈α
ho␈α␈rses␈αa␈α␈re␈αe␈α␈n␈α␈tere␈α␈d␈αin␈α
a␈α
race␈α
an␈α␈d␈α
tha␈α␈t␈αy␈α}ou␈α
kn␈α␈o␈α␈w␈αn␈α␈oth␈α␈ing␈α
wha␈α␈tev␈α␈e␈α␈r
␈βαR␈↓ α␈εβab␈α␈ou␈α␈t␈α∞their␈α∞q␈α␈uali|c␈α␈ation␈α␈s.␈α∃Ass␈α␈i␈α↓g␈α␈n␈α∞to␈α∞th␈α␈ese␈α∞h␈α␈orse␈α␈s␈α∞the␈α∞d␈α␈igits␈α∞0␈α∞to␈α∞9␈α␈,␈α∂i␈α↓n␈α
arb␈α␈itrary
␈βαy␈↓ α␈εβfash␈α␈ion,␈αan␈α␈d␈αa␈α␈fter␈αthe␈αra␈α␈ce␈αu␈α␈se␈αthe␈αwin␈α␈ner's␈αd␈α␈i␈α↓g␈α␈i␈α↓t.
␈ββ,␈↓ ↓g␈ε∪2.␈↓ α␈εβ[␈ε	M22␈↓ αX␈εβ]␈α⊗In␈αa␈αra␈α␈nd␈α␈om␈αsequ␈α␈en␈α␈ce␈αof␈α
a␈αm␈α␈i␈α↓llion␈αd␈α␈ecimal␈αdigits,␈α
wh␈α␈at␈αi␈α↓s␈αth␈α␈e␈αprob␈α␈ab␈α␈il␈α↓ity
␈ββT␈↓ ↓H␈εβth␈α␈at␈αth␈α␈ere␈αar␈α␈e␈αexa␈α␈ctly␈α10␈α␈0,00␈α␈0␈αof␈αea␈α␈ch␈αp␈α␈ossible␈αd␈α␈i␈α↓g␈α␈it?
␈β∧π␈↓ ↓g␈ε∪3.␈↓ α␈εβ[␈ε	10␈↓ α;␈εβ]␈α⊗What␈αn␈α}um␈α␈b␈α␈er␈αfollo␈α␈ws␈α10␈α␈101␈α␈010␈α␈10␈αin␈α
the␈αmid␈α␈dle-squ␈α␈are␈αm␈α␈etho␈α␈d?
␈β∧:␈↓ ↓g␈ε∪4.␈↓ α␈εβ[␈ε	10␈↓ α;␈εβ]␈α⊗Wh␈α␈y␈απcan␈α␈'t␈αλth␈α␈e␈αλv␈α␈alue␈απof␈↓ ¬%␈ε	X␈↓ ¬H␈εβbe␈απzero␈απwhen␈απste␈α␈p␈απK11␈απof␈αλAlgo␈α␈rithm␈απK␈αλis␈απperfo␈α␈rmed␈α␈?
␈β∧b␈↓ ↓H␈εβWh␈α␈at␈αw␈α␈ou␈α␈l␈α↓d␈α
be␈αwro␈α␈ng␈αwith␈α
the␈αa␈α␈l␈α↓g␈α␈orithm␈α
i␈α↓f␈↓ εR␈ε	X␈↓ εy␈εβc␈α␈ou␈α␈l␈α↓d␈α
be␈αze␈α␈ro?
␈β¬∃␈↓ ↓g␈ε∪5.␈↓ α␈εβ[␈ε	15␈↓ α;␈εβ]␈α⊗Exp␈α␈l␈α↓a␈α␈in␈α
wh␈α␈y␈α␈,␈α∞i␈α↓n␈αan␈α␈y␈αcase,␈α∞Algo␈α␈rithm␈α
K␈α
sh␈α␈ould␈α
n␈α␈ot␈α
b␈α␈e␈α
exp␈α␈ected␈αto␈α
pro␈α}vide
␈β¬=␈↓ ↓H␈εβ\␈α␈i␈α↓n␈α␈|n␈α␈itely␈α∞man␈α}y"␈α∞ra␈α␈nd␈α␈om␈α∞n␈α␈u␈α␈m␈α␈b␈α␈ers,␈α⊂in␈α∞th␈α␈e␈α∞sense␈α∞th␈α␈at␈α∞(ev␈α␈e␈α␈n␈α∞i␈α↓f␈α∞th␈α␈e␈α∂c␈α␈oincid␈α␈enc␈α␈e␈α∂g␈α␈i␈α↓v␈α}en
␈β¬d␈↓ ↓H␈εβin␈α
Ta␈α␈ble␈α
1␈α
ha␈α␈d␈α
n␈α␈ot␈α
occ␈α␈urred␈α␈)␈α∞o␈α␈ne␈α
k␈α␈no␈α}ws␈α∞in␈α
a␈α␈dv␈α␈an␈α␈ce␈α
tha␈α␈t␈α∞a␈α␈n␈α␈y␈α
se␈α␈qu␈α␈ence␈α
g␈α␈ene␈α␈rated␈αby
␈βε␈↓ ↓H␈εβAlgo␈α␈rithm␈αK␈αwill␈αe␈α␈v␈α␈en␈α}tua␈α␈l␈α↓ly␈αb␈α␈e␈αp␈α␈eriodic.
␈βε;␈↓ ↓;␈ε↓x
␈βε?␈↓ ↓g␈ε∪6.␈↓ α␈εβ[␈ε	M20␈↓ αX␈εβ]␈α⊗S␈α␈up␈α␈po␈α␈se␈α
th␈α␈at␈α
w␈α␈e␈αwan␈α␈t␈αto␈α
g␈α␈ene␈α␈rate␈αa␈α
seq␈α␈uen␈α␈ce␈αof␈α
in␈α␈te␈α␈gers␈↓ 	H␈ε	X␈↓ 	l␈εβ,␈↓ 
β␈ε	X␈↓ 
&␈εβ,␈↓ 
=␈ε	X␈↓ 
`␈εβ,␈↓ 
w␈εβ.␈αε.␈α¬.␈↓ #␈εβ,
␈βεI␈↓ 	`␈εε0␈↓ 
~␈εε1␈↓ 
T␈εε2
␈βεf␈↓ ↓H␈εβin␈α
th␈α␈e␈α
ran␈α␈ge␈α
0␈ε↔␈α
∀␈↓ βU␈ε	X␈↓ ∧
␈εβ<␈↓ ∧8␈ε	m␈↓ ∧U␈εβ.␈α∩L␈α↓e␈α␈t␈↓ ¬0␈ε	f␈↓ ¬@␈εβ(␈↓ ¬K␈ε	x␈↓ ¬\␈εβ)␈α
be␈α
an␈α}y␈α
fun␈α␈ction␈α
su␈α␈ch␈α
th␈α␈at␈α
0␈ε↔␈α
∀␈↓ 	O␈ε	x␈↓ 	n␈εβ<␈↓ 
≤␈ε	m␈↓ 
G␈εβimp␈α␈li␈α↓e␈α␈s
␈βεq␈↓ βl␈εn
␈βπ∞␈↓ ↓H␈εβ0␈ε↔␈α	∀␈↓ α␈ε	f␈↓ α≤␈εβ(␈↓ α'␈ε	x␈↓ α8␈εβ)␈α
<␈↓ αw␈ε	m␈↓ β∃␈εβ.␈αC␈α␈onsid␈α␈er␈α
a␈α
seq␈α␈uen␈α␈ce␈α
form␈α␈ed␈α
b␈α␈y␈α
th␈α␈e␈α
rule␈↓ πp␈ε	X␈↓ λF␈εβ=␈↓ λq␈ε	f␈↓ 	↓␈εβ(␈↓ 	␈ε	X␈↓ 	3␈εβ).␈α↔(E␈α↓x␈α␈am␈α␈ples␈α
are
␈βπ→␈↓ λπ␈εn␈↓ λ↔␈εε+1␈↓ 	#␈εn
␈βπ6␈↓ ↓H␈εβth␈α␈e␈αmid␈α␈dle-squ␈α␈are␈αm␈α␈etho␈α␈d␈αan␈α␈d␈αAlgo␈α␈ri␈α↓t␈α␈hm␈αK.)
␈βπi␈↓ ↓e␈εβa)␈↓ α␈εβSh␈α␈o␈α␈w␈αt␈α␈hat␈αthe␈αsequ␈α␈en␈α␈ce␈αis␈αu␈α␈lti␈α↓m␈α␈ately␈αpe␈α␈ri␈α↓o␈α␈dic,␈αin␈αthe␈αsens␈α␈e␈αth␈α␈at␈αth␈α␈ere␈αexist␈αn␈α}um␈α␈-
␈βλ⊂␈↓ α␈εβbe␈α␈rs␈↓ αS␈ε	∃␈↓ αs␈εβan␈α␈d␈↓ β5␈ε	⊗␈↓ βT␈εβfo␈α␈r␈αwhich␈αth␈α␈e␈αva␈α␈l␈α↓u␈α␈es␈↓ ε␈ε	X␈↓ ε/␈εβ,␈↓ εE␈ε	X␈↓ εh␈εβ,␈↓ ε}␈εβ.␈αε.␈αε.␈↓ π*␈εβ,␈↓ π@␈ε	X␈↓ πf␈εβ,␈↓ π|␈εβ.␈αε.␈α¬.␈↓ λ(␈εβ,␈↓ λ>␈ε	X␈↓ 	?␈εβare␈αd␈α␈istinct,␈αbu␈α␈t
␈βλ≠␈↓ ε"␈εε0␈↓ ε\␈εε1␈↓ πW␈ε⊗␈↓ λU␈ε⊗␈↓ λd␈εε+␈↓ λ⎇␈ε∃␈↓ 	
␈ε~␈␈εε1
␈βλ8␈↓ α␈ε	X␈↓ αg␈εβ=␈↓ β∪␈ε	X␈↓ βF␈εβwhe␈α␈n␈↓ ∧≡␈ε	n␈↓ ∧<␈ε↔∃␈↓ ∧h␈ε	⊗␈↓ ∧z␈εβ.␈α∞Find␈αthe␈αmax␈α␈im␈α␈um␈αan␈α␈d␈αmin␈α␈i␈α↓m␈α}um␈αposs␈α␈i␈α↓b␈α␈le␈αva␈α␈lues␈αo␈α␈f␈↓ ~␈ε	⊗
␈βλC␈↓ α#␈εn␈↓ α3␈εε+␈↓ αM␈ε∃␈↓ β*␈εn
␈βλ`␈↓ α␈εβan␈α␈d␈↓ αM␈ε	∃␈↓ α`␈εβ.
␈β	π␈↓ ↓c␈εβb)␈↓ α␈εβ(R.␈α
W␈α↓.␈α
Flo␈α␈y␈α␈d.)␈α≥Sh␈α␈o␈α␈w␈α
th␈α␈at␈α
th␈α␈ere␈α
e␈α␈xists␈α
an␈↓ π␈ε	n␈↓ π,␈εβ>␈α
0␈α
s␈α␈uch␈αtha␈α␈t␈↓ 	∂␈ε	X␈↓ 	C␈εβ=␈↓ 	q␈ε	X␈↓ 
%␈εβ;␈α∞a␈α␈nd␈αthe
␈β	∩␈↓ 	&␈εn␈↓ 
λ␈εε2␈↓ 
∀␈εn
␈β	/␈↓ α␈εβsma␈α␈l␈α↓lest␈αsu␈α␈ch␈α
valu␈α␈e␈αof␈↓ ∧W␈ε	n␈↓ ∧v␈εβlies␈αin␈αth␈α␈e␈αran␈α␈ge␈↓ εj␈ε	⊗␈↓ π¬␈ε↔∀␈↓ π0␈ε	n␈↓ πM␈ε↔∀␈↓ πx␈ε	⊗␈↓ λ⊃␈εβ+␈↓ λ:␈ε	∃␈↓ λM␈εβ.␈αF␈α↓u␈α␈rthe␈α␈rmore␈α
the␈αv␈α␈alue
␈β	W␈↓ α␈εβof␈↓ α3␈ε	X␈↓ αe␈εβi␈α↓s␈αu␈α␈niqu␈α␈e␈αin␈αth␈α␈e␈αsen␈α␈se␈αtha␈α␈t␈αi␈α↓f␈↓ ε∂␈ε	X␈↓ ε@␈εβ=␈↓ εj␈ε	X␈↓ π)␈εβan␈α␈d␈↓ πj␈ε	X␈↓ λ↔␈εβ=␈↓ λA␈ε	X␈↓ λq␈εβ,␈αthen␈↓ 	Q␈ε	X␈↓ 	}␈εβ=␈↓ 
(␈ε	X␈↓ 
P␈εβ.
␈β	a␈↓ αJ␈εn␈↓ ε&␈εn␈↓ π↓␈εε2␈↓ π∞␈εn␈↓ λ↓␈εr␈↓ λX␈εε2␈↓ λe␈εr␈↓ 	h␈εr␈↓ 
@␈εn
␈β
ε␈↓ ↓;␈ε↓x
␈β

␈↓ ↓g␈ε∪7.␈↓ α␈εβ[␈ε	M21␈↓ αX␈εβ]␈α⊗(R.␈α
P.␈α
Bren␈α}t,␈α
19␈α␈77.)␈α≤Let␈↓ ¬r␈ε	#␈↓ ε␈εβ(␈↓ ε␈ε	n␈↓ ε∨␈εβ)␈α
b␈α␈e␈α
th␈α␈e␈αl␈α↓e␈α␈ast␈αpo␈α␈w␈α␈er␈αof␈α2␈αtha␈α␈t␈α
is␈αl␈α↓e␈α␈ss␈α
th␈α␈an␈αo␈α␈r
␈β
1␈↓ ↓H␈εβe␈α␈qua␈α␈l␈αto␈↓ αG␈ε	n␈↓ α[␈εβ;␈αth␈α}us,␈αfor␈αex␈α␈am␈α␈ple,␈↓ ¬α␈ε	#␈↓ ¬⊂␈εβ(15)␈α	=␈α
8␈α
an␈α␈d␈↓ εX␈ε	#␈↓ εf␈εβ(␈↓ εq␈ε	#␈↓ ε␈␈εβ(␈↓ π
␈ε	n␈↓ π≡␈εβ))␈α	=␈↓ πh␈ε	#␈↓ πv␈εβ(␈↓ λ↓␈ε	n␈↓ λ∃␈εβ).
␈β
d␈↓ ↓e␈εβa)␈↓ α␈εβSh␈α␈o␈α␈w␈αth␈α␈at,␈αin␈α
terms␈α
of␈αth␈α␈e␈αn␈α␈otation␈α
in␈α
ex␈α␈er␈α␈ci␈α↓s␈α␈e␈α6,␈αth␈α␈ere␈αe␈α␈xists␈αa␈α␈n␈↓ 	A␈ε	n␈↓ 	↑␈εβ>␈α	0␈αsu␈α␈ch␈α
tha␈α␈t
␈β␈↓ α␈ε	X␈↓ α=␈εβ=␈↓ αg␈ε	X␈↓ βP␈εβ.␈αF␈α↓in␈α␈d␈α
a␈α
for␈α␈m␈α␈ula␈α
th␈α␈at␈α
ex␈α␈pres␈α␈ses␈α
the␈α
lea␈α␈st␈α
such␈↓ λn␈ε	n␈↓ 	␈εβi␈α↓n␈α	terms␈α
o␈α␈f␈↓ 
4␈ε	⊗␈↓ 
P␈εβan␈α␈d␈↓ ⊂␈ε	∃␈↓ #␈εβ.
␈β↔␈↓ α#␈εn
␈β_␈↓ α}␈ε#␈↓ β
␈εε(␈↓ β∩␈εn␈↓ β"␈εε)␈ε~␈α↓␈␈εε1
␈β4␈↓ ↓c␈εβb)␈↓ α␈εβApp␈α␈ly␈α
th␈α␈i␈α↓s␈α
r␈α␈esult␈α
to␈α
d␈α␈esign␈α	an␈α	algor␈α␈i␈α↓th␈α␈m␈α
th␈α␈at␈α
ca␈α␈n␈α
b␈α␈e␈α
use␈α␈d␈α
in␈α
co␈α␈nju␈α␈nctio␈α␈n␈α
with␈α
a␈α␈n␈α␈y
␈β[␈↓ α␈εβran␈α␈do␈α␈m-n␈α␈u␈α␈m␈α␈be␈α␈r␈α
ge␈α␈nera␈α␈tor␈αof␈α
th␈α␈e␈α
ty␈α␈pe␈↓ εF␈ε	X␈↓ π∨␈εβ=␈↓ πL␈ε	f␈↓ π\␈εβ(␈↓ πg␈ε	X␈↓ λ∞␈εβ)␈α↓,␈α
to␈αp␈α␈rev␈α␈en␈α}t␈α
it␈α
fro␈α␈m␈α
c␈α␈y␈α␈cling
␈βf␈↓ ε]␈εn␈↓ εm␈εε+␈α↓1␈↓ π}␈εn
␈ββ␈↓ α␈εβind␈α␈e|n␈α␈itely.␈α∩Yo␈α␈ur␈α
algo␈α␈ri␈α↓th␈α␈m␈α
sho␈α␈uld␈α
ca␈α␈lculate␈α
th␈α␈e␈α
per␈α␈i␈α↓o␈α␈d␈α
leng␈α␈th␈↓ 	=␈ε	∃␈↓ 	Q␈εβ,␈α∞a␈α␈nd␈α
it␈α
sho␈α␈uld
␈β+␈↓ α␈εβus␈α␈e␈αon␈α␈l␈α↓y␈αa␈αsma␈α␈ll␈α
a␈α␈mou␈α␈n␈α␈t␈αo␈α␈f␈αmemo␈α␈ry␈αsp␈α␈ace←y␈α}ou␈αm␈α}ust␈αn␈α␈ot␈αsimp␈α␈l␈α↓y␈αstore␈αall␈αof␈αthe
␈βR␈↓ α␈εβco␈α␈mpu␈α␈ted␈αse␈α␈qu␈α␈ence␈α
valu␈α␈es!
␈β
¬␈↓ ↓g␈ε∪8.␈↓ α␈εβ[␈ε	28␈↓ α;␈εβ]␈α⊗Ma␈α␈k␈α␈e␈αλa␈απco␈α␈mplete␈απexa␈α␈mina␈α␈ti␈α↓o␈α␈n␈αλo␈α␈f␈αλth␈α␈e␈αλmidd␈α␈le-squ␈α␈are␈αλm␈α␈etho␈α␈d␈απi␈α↓n␈απth␈α␈e␈αλca␈α␈se␈αλof␈αλt␈α␈w␈α␈o␈α␈-
␈β
-␈↓ ↓H␈εβd␈α␈igit␈α
d␈α␈ecima␈α␈l␈α
n␈α␈u␈α␈m␈α␈b␈α␈ers.␈α∃(a)␈α	W␈α↓e␈α	mig␈α␈h␈α␈t␈α	start␈α	the␈α	p␈α␈roces␈α␈s␈α
o␈α␈ut␈α	wi␈α↓th␈αλan␈α␈y␈α	o␈α␈f␈α
th␈α␈e␈α	100␈α	p␈α␈ossib␈α␈l␈α↓e
␈β
T␈↓ ↓H␈εβv␈α␈alue␈α␈s␈α
00,␈α
01,␈↓ β⊗␈εβ.␈αε.␈αε.␈↓ βC␈εβ,␈α
99␈α␈.␈αHo␈α␈w␈α
man␈α}y␈α
of␈α
th␈α␈ese␈α
v␈α␈alues␈α
lea␈α␈d␈α
ultima␈α␈tely␈α
to␈α
th␈α␈e␈α
rep␈α␈eatin␈α␈g␈α
cy␈α␈c␈α␈l␈α↓e
␈β
|␈↓ ↓H␈εβ0␈α␈0,␈α00,␈↓ α3␈εβ.␈αε.␈αε.␈↓ α`␈εβ?␈α[␈ε⊂E␈α↓x␈α␈amp␈α␈le:␈εβ␈αS␈α␈tarting␈α
wi␈α↓th␈α
43,␈αw␈α␈e␈αobta␈α␈in␈αthe␈αse␈α␈que␈α␈nce␈α4␈α␈3,␈α8␈α␈4,␈α05,␈α02,␈α00␈α␈,␈α00␈α␈,
␈β∞$␈↓ ↓H␈εβ0␈α␈0,␈↓ ↓{␈εβ.␈αε.␈αε.␈↓ α'␈εβ.␈α↓]␈α∩(b)␈αλHo␈α␈w␈αλman␈α}y␈αλp␈α␈ossible␈αλ|n␈α␈al␈αλcy␈α␈c␈α␈l␈α↓es␈αλa␈α␈re␈αλthere␈α␈?␈αHo␈α}w␈α	lon␈α␈g␈αλis␈α	th␈α␈e␈αλlong␈α␈est␈αλcy␈α␈c␈α␈l␈α↓e?␈α⊃(␈α↓c␈α␈)
␈β∞K␈↓ ↓H␈εβWh␈α␈at␈αstarting␈αv␈α␈alue␈αo␈α␈r␈αv␈α␈alues␈αwill␈αgiv␈α␈e␈αth␈α␈e␈αl␈α↓a␈α␈rgest␈αn␈α␈u␈α␈m␈α␈b␈α␈er␈αo␈α␈f␈αd␈α␈i␈α↓s␈α␈ti␈α↓n␈α␈ct␈αelemen␈α}ts␈αb␈α␈efore
␈β∞s␈↓ ↓H␈εβth␈α␈e␈αseq␈α␈uen␈α␈ce␈αrep␈α␈eats␈α␈?
␈β∂&␈↓ ↓g␈ε∪9.␈↓ α␈εβ[␈ε	M14␈↓ αX␈εβ]␈α⊗Pro␈α␈v␈α}e␈α
th␈α␈at␈α
th␈α␈e␈α
m␈α␈i␈α↓d␈α␈dle-sq␈α␈uar␈α␈e␈α
met␈α␈hod␈αu␈α␈si␈α↓n␈α␈g␈α2␈↓ λ∪␈ε	n␈↓ λ'␈εβ-digit␈αn␈α␈um␈α}bers␈αto␈α
th␈α␈e␈α
b␈α␈ase
␈β∂N␈↓ ↓H␈ε	b␈↓ ↓d␈εβha␈α␈s␈α∂the␈α∂fo␈α␈l␈α↓lo␈α␈win␈α␈g␈α∂disad␈α␈va␈α␈n␈α␈ta␈α␈ge:␈α∪If␈α⊂th␈α␈e␈α∂sequ␈α␈en␈α␈ce␈α∂inclu␈α␈des␈α∂a␈α␈n␈α␈y␈α∂n␈α}um␈α␈b␈α␈er␈α∂who␈α␈se␈α∂mos␈α␈t
␈β∂u␈↓ ↓H␈εβsig␈α␈ni|ca␈α␈n␈α␈t␈↓ αf␈ε	n␈↓ β¬␈εβdigits␈αare␈αze␈α␈ro,␈αth␈α␈e␈αsuc␈α␈ceed␈α␈i␈α↓n␈α␈g␈αn␈α␈u␈α␈m␈α␈b␈α␈ers␈αwi␈α↓ll␈αg␈α␈et␈αsmaller␈αan␈α␈d␈αsma␈α␈l␈α↓ler␈αu␈α␈n␈α␈til
␈β⊂≥␈↓ ↓H␈εβz␈α␈ero␈αoc␈α␈curs␈αre␈α␈pea␈α␈tedly␈α␈.
␈β⊂P␈↓ ↓V␈ε∪10.␈↓ α␈εβ[␈ε	M16␈↓ αX␈εβ]␈α⊗Un␈α␈der␈αth␈α␈e␈αa␈α␈ssum␈α␈ption␈α␈s␈αo␈α␈f␈αth␈α␈e␈αpre␈α␈cedin␈α␈g␈αex␈α␈e␈α␈rcise,␈αwh␈α␈at␈αcan␈αy␈α}ou␈αsa␈α␈y␈αab␈α␈ou␈α␈t
␈β⊂w␈↓ ↓H␈εβth␈α␈e␈α	s␈α␈equ␈α␈ence␈αλof␈αλn␈α␈u␈α␈m␈α␈bers␈αλfollo␈α␈wing␈↓ ¬7␈ε	X␈↓ ¬[␈εβi␈α↓f␈αλthe␈ε⊂␈αλleast␈εβ␈αλsi␈α↓g␈α␈ni|c␈α␈an␈α␈t␈↓ λ⊗␈ε	n␈↓ λ3␈εβd␈α␈i␈α↓g␈α␈its␈α	of␈↓ 	/␈ε	X␈↓ 	T␈εβa␈α␈re␈α	z␈α␈ero?␈α
Wha␈α␈t
␈β⊃∨␈↓ ↓H␈εβif␈αthe␈α
l␈α↓e␈α␈ast␈αsign␈α␈i␈α↓|␈α␈can␈α}t␈↓ ∧␈ε	n␈↓ ∧(␈εβ+␈απ1␈αdigits␈αa␈α␈re␈αzero?
␈β∪(

␈β↓Y␈↓ ↓H␈εα8␈↓ α=␈ε∞RA␈α␈NDOM␈α	NUMBERS␈εα␈↓ 
}3.1
␈βα&␈↓ ↓;␈ε↓x
␈βα*␈↓ ↓V␈ε∪11.␈↓ α␈εβ[␈ε	M26␈↓ αX␈εβ]␈α⊗Co␈α␈nside␈α␈r␈απseq␈α␈uen␈α␈ces␈αεof␈απra␈α␈nd␈α␈om-n␈α}um␈α␈b␈α␈er␈αεgen␈α␈erato␈α␈rs␈απh␈α␈avin␈α␈g␈απt␈α␈he␈αεform␈αεdesc␈α␈ri␈α↓b␈α␈ed
␈βαN␈↓ ∃␈εm
␈βαR␈↓ ↓H␈εβin␈αλex␈α␈er␈α␈ci␈α↓s␈α␈e␈α	6.␈α
I␈α↓f␈α	w␈α␈e␈αλcho␈α␈ose␈↓ ∧?␈ε	f␈↓ ∧O␈εβ(␈↓ ∧Z␈ε	x␈↓ ∧k␈εβ)␈α	an␈α␈d␈↓ ¬>␈ε	X␈↓ ¬j␈εβat␈α	ra␈α␈nd␈α␈om,␈α	i␈α↓.e.,␈α
if␈α	w␈α␈e␈α	a␈α␈ssume␈αλtha␈α␈t␈α	each␈αλof␈α	th␈α␈e␈↓ 
x␈ε	m
␈βα\␈↓ ¬U␈εε0
␈βαy␈↓ ↓H␈εβp␈α␈ossib␈α␈l␈α↓e␈α	f␈α↓u␈α␈nc␈α␈ti␈α↓o␈α␈ns␈↓ βR␈ε	f␈↓ βb␈εβ(␈↓ βm␈ε	x␈↓ β}␈εβ)␈α
is␈α
equ␈α␈ally␈α
p␈α␈rob␈α␈able␈α
a␈α␈nd␈α	tha␈α␈t␈α
each␈α	of␈α
th␈α␈e␈↓ λ\␈ε	m␈↓ 	β␈εβpossib␈α␈l␈α↓e␈α	va␈α␈l␈α↓u␈α␈es␈α
of␈↓ 	␈ε	X
␈ββ∧␈↓  ␈εε0
␈ββ!␈↓ ↓H␈εβis␈αλequ␈α␈ally␈αλpro␈α␈ba␈α␈ble,␈α	wha␈α␈t␈αλi␈α↓s␈αλth␈α␈e␈αλprob␈α␈ab␈α␈il␈α↓ity␈αλth␈α␈at␈αλthe␈αλse␈α␈que␈α␈nce␈αλwill␈α	ev␈α}en␈α␈tu␈α␈ally␈αλde␈α␈gen␈α␈erate
␈ββI␈↓ ↓H␈εβin␈α}to␈αa␈αcy␈α␈cle␈αof␈αleng␈α␈th␈↓ ∧	␈ε	∃␈↓ ∧'␈εβ=␈α1?␈α~(␈ε⊂Note:␈εβ␈α
Th␈α␈e␈αa␈α␈ssump␈α␈tion␈α␈s␈αof␈αth␈α␈is␈αpro␈α␈blem␈αgiv␈α␈e␈αa␈αn␈α␈atura␈α␈l
␈ββp␈↓ ↓H␈εβwa␈α␈y␈α
to␈α
think␈α	of␈αa␈α
\␈α␈ran␈α␈dom␈α␈"␈α
rand␈α␈om␈α␈-␈α↓n␈α}um␈α}ber␈α
gen␈α␈era␈α␈tor␈α
of␈αth␈α␈is␈αty␈α␈pe␈α␈.␈αA␈α
meth␈α␈od␈α
su␈α␈ch␈α
a␈α␈s
␈β∧_␈↓ ↓H␈εβAlgo␈α␈rithm␈α
K␈α
may␈α
b␈α␈e␈α
ex␈α␈pecte␈α␈d␈α
to␈α
be␈α␈hav␈α}e␈α
some␈α␈w␈α↓h␈α␈at␈α
lik␈α␈e␈α
the␈α
g␈α␈enera␈α␈tor␈α
con␈α␈sider␈α␈ed␈α
he␈α␈re;
␈β∧?␈↓ ↓H␈εβth␈α␈e␈αa␈α␈nsw␈α␈er␈α
to␈α
this␈αp␈α␈rob␈α␈l␈α↓e␈α␈m␈αg␈α␈i␈α↓v␈α}es␈αa␈α
mea␈α␈sure␈α
of␈αh␈α␈o␈α␈w␈α
\colo␈α␈ssal"␈αth␈α␈e␈α
coinc␈α␈i␈α↓d␈α␈enc␈α␈e␈αo␈α␈f␈αTab␈α␈l␈α↓e
␈β∧g␈↓ ↓H␈εβ1␈α
really␈αis.)
␈β¬∃␈↓ ↓;␈ε↓x
␈β¬→␈↓ ↓V␈ε∪12.␈↓ α␈εβ[␈ε	M31␈↓ αX␈εβ]␈α⊗Un␈α␈der␈αλth␈α␈e␈αλassu␈α␈mp␈α␈ti␈α↓o␈α␈ns␈αλo␈α␈f␈α	th␈α␈e␈αλp␈α␈reced␈α␈i␈α↓n␈α␈g␈αλex␈α}ercise,␈α	wh␈α␈at␈αλis␈αλthe␈αλa␈α␈v␈α␈era␈α␈ge␈αλlen␈α␈gth
␈β¬A␈↓ ↓H␈εβo␈α␈f␈αth␈α␈e␈α
|n␈α␈al␈αc␈α␈y␈α␈cle?␈αWh␈α␈at␈α
i␈α↓s␈α
th␈α␈e␈α
av␈α␈e␈α␈rage␈α
len␈α␈gth␈α
o␈α␈f␈αth␈α␈e␈αs␈α␈equ␈α␈ence␈α
b␈α␈efore␈α
it␈α
beg␈α␈i␈α↓n␈α␈s␈α
to␈α
cy␈α␈c␈α␈l␈α↓e␈α␈?
␈β¬i␈↓ ↓H␈εβ(In␈αλthe␈αλno␈α␈tation␈αλof␈α	e␈α␈x␈α␈ercise␈αλ6,␈α
w␈α␈e␈αλwi␈α↓sh␈αλto␈αλexa␈α␈mine␈αλthe␈αλav␈α␈e␈α␈rage␈αλva␈α␈l␈α↓u␈α␈es␈α	o␈α␈f␈↓ 	I␈ε	∃␈↓ 	e␈εβand␈αλof␈↓ 
H␈ε	⊗␈↓ 
←␈εβ+␈↓ ¬␈ε	∃␈↓ _␈εβ.)
␈βε≠␈↓ ↓V␈ε∪13.␈↓ α␈εβ[␈ε	M42␈↓ αX␈εβ]␈α⊗If␈↓ β_␈ε	f␈↓ β'␈εβ(␈↓ β3␈ε	x␈↓ βD␈εβ)␈αis␈αc␈α␈hose␈α␈n␈α
at␈αra␈α␈nd␈α␈om␈α
i␈α↓n␈α
th␈α␈e␈αsen␈α␈se␈α
of␈αex␈α}ercise␈α
11,␈αwh␈α␈at␈αis␈α
the␈α
av␈α␈e␈α␈rage
␈βεC␈↓ ↓H␈εβlen␈α␈gth␈απof␈αλthe␈ε⊂␈απl␈α↓o␈α␈nge␈α␈st␈εβ␈αλcy␈α␈c␈α␈l␈α↓e␈αλo␈α␈bta␈α␈i␈α↓n␈α␈ab␈α␈l␈α↓e␈απby␈απvary␈α␈ing␈αλt␈α␈he␈αλsta␈α␈rti␈α↓n␈α␈g␈αλv␈α␈alue␈↓ 	␈ε	X␈↓ 	.␈εβ?␈α∩(␈ε⊂No␈α␈te:␈εβ␈α
We␈αλh␈α␈av␈α␈e
␈βεM␈↓ 	"␈εε0
␈βεj␈↓ ↓H␈εβa␈α␈l␈α↓r␈α␈ead␈α␈y␈αλc␈α␈ons␈α␈i␈α↓d␈α␈ered␈απth␈α␈e␈αλa␈α␈nalog␈α␈ou␈α␈s␈αλp␈α␈roblem␈απin␈απthe␈απcase␈απtha␈α␈t␈↓ λ¬␈ε	f␈↓ λ∃␈εβ(␈↓ λ ␈ε	x␈↓ λ1␈εβ)␈αλis␈αλa␈απran␈α␈do␈α␈m␈αλp␈α␈erm␈α␈u␈α␈tation␈α␈;
␈βπ∩␈↓ ↓H␈εβse␈α␈e␈αex␈α␈e␈α␈rcise␈α1.3.3↑␈α␈23.)
␈βπD␈↓ ↓V␈ε∪14.␈↓ α␈εβ[␈ε	M38␈↓ αX␈εβ]␈α⊗If␈↓ β_␈ε	f␈↓ β'␈εβ(␈↓ β3␈ε	x␈↓ βD␈εβ)␈αis␈αc␈α␈hose␈α␈n␈α
at␈αra␈α␈nd␈α␈om␈α
i␈α↓n␈α
th␈α␈e␈αsen␈α␈se␈α
of␈αex␈α}ercise␈α
11,␈αwh␈α␈at␈αis␈α
the␈α
av␈α␈e␈α␈rage
␈βπl␈↓ ↓H␈εβn␈α}um␈α␈b␈α␈er␈αo␈α␈f␈αdistin␈α␈ct␈α|␈α␈nal␈αc␈α␈y␈α␈cles␈αo␈α␈bta␈α␈i␈α↓n␈α␈ab␈α␈l␈α↓e␈α
by␈α
v␈α␈ary␈α␈i␈α↓n␈α␈g␈αth␈α␈e␈αsta␈α␈rting␈α
va␈α␈l␈α↓u␈α␈e?␈α_[Cf.␈αe␈α␈x␈α␈erc␈α␈i␈α↓se
␈βλ∪␈↓ ↓H␈εβ8␈α␈(b).]
␈βλF␈↓ ↓V␈ε∪15.␈↓ α␈εβ[␈ε	M15␈↓ αX␈εβ]␈α⊗If␈↓ β∀␈ε	f␈↓ β$␈εβ(␈↓ β/␈ε	x␈↓ βA␈εβ)␈απis␈απcho␈α␈sen␈απa␈α␈t␈αλra␈α␈nd␈α␈om␈απin␈απth␈α␈e␈απsens␈α␈e␈απof␈απex␈α␈erc␈α␈i␈α↓se␈απ1␈α␈1,␈αλwha␈α␈t␈αλis␈απth␈α␈e␈απprob␈α␈ab␈α␈il␈α↓ity
␈βλm␈↓ ↓H␈εβth␈α␈at␈αn␈α␈on␈α␈e␈αof␈αthe␈α|␈α␈na␈α␈l␈αc␈α␈y␈α␈cles␈αh␈α␈as␈αleng␈α␈th␈α1␈α␈,␈αreg␈α␈ard␈α␈l␈α↓e␈α␈ss␈αof␈αthe␈αc␈α␈ho␈α␈i␈α↓ce␈α
of␈↓ 	3␈ε	X␈↓ 	W␈εβ?
␈βλx␈↓ 	J␈εε0
␈β	 ␈↓ ↓V␈ε∪16.␈↓ α␈εβ[␈ε	15␈↓ α;␈εβ]␈α⊗A␈αseq␈α␈uen␈α␈ce␈αgen␈α␈erate␈α␈d␈αa␈α␈s␈αin␈αex␈α␈e␈α␈rcise␈α6␈αm␈α␈u␈α␈st␈αb␈α␈egin␈αto␈αre␈α␈pea␈α␈t␈αafte␈α␈r␈αat␈αmost␈↓ ∂␈ε	m
␈β	G␈↓ ↓H␈εβv␈α␈alue␈α␈s␈αλha␈α␈v␈α␈e␈αλb␈α␈een␈απge␈α␈nera␈α␈ted.␈α
S␈α␈up␈α␈pos␈α␈e␈αλw␈α␈e␈αλge␈α␈nera␈α␈l␈α↓ize␈απthe␈απmeth␈α␈od␈απso␈αλth␈α␈at␈↓ 	8␈ε	X␈↓ 

␈εβd␈α␈epe␈α␈nd␈α␈s␈αλon
␈β	R␈↓ 	O␈εn␈↓ 	←␈εε+1
␈β	o␈↓ ↓H␈ε	X␈↓ α≥␈εβa␈α␈s␈αλwe␈α␈l␈α↓l␈αλa␈α␈s␈αλon␈↓ βS␈ε	X␈↓ β{␈εβ;␈α	forma␈α␈l␈α↓ly␈α␈,␈α	let␈↓ ¬F␈ε	f␈↓ ¬V␈εβ(␈↓ ¬a␈ε	x␈↓ ¬r␈εβ,␈↓ ε↓␈ε	y␈↓ ε∀␈εβ)␈αλb␈α␈e␈αλa␈αλfu␈α␈nc␈α␈ti␈α↓o␈α␈n␈αλsu␈α␈ch␈αλt␈α␈hat␈αλ0␈ε↔␈αλ∀␈↓ 	;␈ε	x␈↓ 	L␈εβ,␈↓ 	[␈ε	y␈↓ 	w␈εβ<␈↓ 
!␈ε	m␈↓ 
G␈εβimp␈α␈li␈α↓e␈α␈s
␈β	z␈↓ ↓←␈εn␈↓ ↓o␈ε~␈␈εε1␈↓ βk␈εn
␈β
↔␈↓ ↓H␈εβ0␈ε↔␈α	∀␈↓ α∞␈ε	f␈↓ α≡␈εβ(␈↓ α)␈ε	x␈↓ α:␈εβ,␈↓ αI␈ε	y␈↓ α[␈εβ)␈α<␈↓ β≤␈ε	m␈↓ β9␈εβ.␈α
The␈αsequ␈α␈enc␈α␈e␈αis␈αc␈α␈onstr␈α␈ucted␈αb␈α␈y␈αselecting␈↓ λ,␈ε	X␈↓ λ[␈εβan␈α␈d␈↓ 	≥␈ε	X␈↓ 	L␈εβarb␈α␈itrarily,␈αa␈α␈nd
␈β
!␈↓ λC␈εε0␈↓ 	4␈εε1
␈β
>␈↓ ↓H␈εβth␈α␈en␈α
l␈α↓et␈α␈ti␈α↓n␈α␈g
␈β
f␈↓ ∧6␈ε	X␈↓ ¬
␈εβ=␈↓ ¬7␈ε	f␈↓ ¬G␈εβ(␈↓ ¬R␈ε	X␈↓ ¬y␈εβ,␈↓ ελ␈ε	X␈↓ εU␈εβ)␈↓ π)␈εβfo␈α␈r␈↓ π\␈ε	n␈↓ πz␈εβ>␈α	0.
␈β
p␈↓ ∧M␈εn␈↓ ∧]␈εε+␈α↓1␈↓ ¬i␈εn␈↓ ε∨␈εn␈↓ ε0␈ε~␈␈εε1
␈β#␈↓ ↓H␈εβWh␈α␈at␈αis␈αthe␈αma␈α␈xim␈α␈u␈α␈m␈αpe␈α␈ri␈α↓o␈α␈d␈αco␈α␈nce␈α␈i␈α↓v␈α␈ab␈α␈l␈α↓y␈α
atta␈α␈i␈α↓n␈α␈ab␈α␈l␈α↓e␈α
i␈α↓n␈α
this␈αca␈α␈se?
␈βU␈↓ ↓V␈ε∪17.␈↓ α␈εβ[␈ε	10␈↓ α;␈εβ]␈α⊗Gen␈α␈eralize␈α	th␈α␈e␈α	situa␈α␈tion␈αλi␈α↓n␈αλthe␈αλprev␈α␈iou␈α␈s␈α	ex␈α␈e␈α␈rcise␈α	so␈α	th␈α␈at␈↓ λ␈␈ε	X␈↓ 	U␈εβd␈α␈ep␈α␈end␈α␈s␈α	on␈αλthe
␈β`␈↓ 	⊗␈εn␈↓ 	&␈εε+1
␈β⎇␈↓ ↓H␈εβp␈α␈rece␈α␈ding␈↓ α]␈ε	k␈↓ αy␈εβv␈α␈alues␈αo␈α␈f␈αt␈α␈he␈αseq␈α␈uen␈α␈ce.
␈β/␈↓ ↓V␈ε∪18.␈↓ α␈εβ[␈ε	M20␈↓ αX␈εβ]␈α⊗In␈α}v␈α␈en␈α}t␈α∞a␈α
m␈α␈etho␈α␈d␈α
an␈α␈alog␈α␈ou␈α␈s␈α∞to␈αthat␈α
o␈α␈f␈α∞e␈α␈x␈α␈ercise␈α
7␈α
fo␈α␈r␈α∞|␈α␈nd␈α␈ing␈α
cy␈α}cles␈α
in␈α
the
␈βW␈↓ ↓H␈εβg␈α␈ene␈α␈ral␈αform␈αof␈αra␈α␈nd␈α␈om-n␈α}um␈α␈b␈α␈er␈αgen␈α␈era␈α␈tor␈αdiscu␈α␈ssed␈α
i␈α↓n␈α
ex␈α␈e␈α␈rcise␈α17.
␈β
	␈↓ ↓V␈ε∪19.␈↓ α␈εβ[␈ε	M48␈↓ αX␈εβ]␈α⊗S␈α␈olv␈α␈e␈αλth␈α␈e␈αλpro␈α␈blems␈αλo␈α␈f␈α	e␈α␈x␈α␈ercises␈αλ1␈α␈1␈αλthro␈α␈ug␈α␈h␈αλ15␈αλfo␈α␈r␈αλthe␈αλmo␈α␈re␈αλgen␈α␈eral␈αλca␈α␈se␈αλtha␈α␈t
␈β
)␈↓ 
∞␈ε
k
␈β
-␈↓ 	v␈εm
␈β
1␈↓ ↓H␈ε	X␈↓ α"␈εβde␈α␈pen␈α␈ds␈α
o␈α␈n␈α
the␈α
p␈α␈rece␈α␈ding␈↓ ¬(␈ε	k␈↓ ¬E␈εβva␈α␈lues␈α
of␈α
th␈α␈e␈α
sequ␈α␈enc␈α␈e;␈α∂e␈α␈ach␈α
o␈α␈f␈α∞t␈α␈he␈↓ 	Y␈ε	m␈↓ 
'␈εβfun␈α␈ction␈α␈s
␈β
<␈↓ ↓←␈εn␈↓ ↓o␈εε+1
␈β
Y␈↓ ↓H␈ε	f␈↓ ↓W␈εβ(␈↓ ↓c␈ε	x␈↓ ↓␈␈εβ,␈↓ α
␈εβ.␈αε.␈αε.␈↓ α:␈εβ,␈↓ αI␈ε	x␈↓ αe␈εβ)␈α
is␈α
to␈α	be␈α	con␈α␈si␈α↓d␈α␈ered␈α	eq␈α␈ua␈α␈l␈α↓ly␈α	pro␈α␈ba␈α␈ble.␈α⊗(␈ε⊂Not␈α␈e:␈εβ␈αThe␈α	n␈α␈u␈α␈m␈α␈b␈α␈er␈α
of␈α	f␈α↓u␈α␈nc␈α␈ti␈α↓o␈α␈ns␈α	tha␈α␈t
␈β
c␈↓ ↓r␈εε1␈↓ αX␈εk
␈β∞␈↓ ↓H␈εβy␈α␈ield␈αth␈α␈e␈ε⊂␈αmax␈α␈i␈α↓m␈α}um␈εβ␈αp␈α␈eriod␈α
i␈α↓s␈αa␈α␈naly␈α␈zed␈αin␈α
ex␈α␈er␈α␈ci␈α↓s␈α␈e␈α2.3.4.2↑␈α␈23.)
␈β∪(/FONT#1=cmathx[XGP,SYS]=xx/FONT#2=cmr10[XGP,SYS]=!"'()+,-./0123456789:;<=>?ABCDEFGHIJKLMNOPRSTUVWY[\]↑←abcdefghijklmnopqrstuvwxyz{|⎇}␈␈/FONT#3=cmr9[XGP,SYS]=!"'()+,-.0123456789:;<=>?ABCDEFGHIKLMNOPRSTUWY[\]↑←abcdefghijklmnopqrstuvwxyz||/FONT#4=cmr8[XGP,SYS]=01BEMRSUU/FONT#5=cmr7[XGP,SYS]=0125899/FONT#6=cmr6[XGP,SYS]=()+0122/FONT#8=cmi10[XGP,SYS]=XYZZ/FONT#9=cmi9[XGP,SYS]=∃⊗#01234568MXYbfkmnxyy/FONT#12=cmi6[XGP,SYS]=∃⊗#kmnrr/FONT#13=cmi5[XGP,SYS]=kk/FONT#14=cmsc10[XGP,SYS]=ABCDEIMNORSTUU/FONT#15=cms10[XGP,SYS]="'-.CDJMNRS\abcdefghiklmnopqrstuwyzz/FONT#16=cms9[XGP,SYS]=:ENaegilmnopstuxx/FONT#18=cmb10[XGP,SYS]=.0123456789AKghilmortt/FONT#19=cmb9[XGP,SYS]=.01234567899/FONT#22=cmsy10[XGP,SYS]=α∃ bc⎇⎇/FONT#23=cmsy9[XGP,SYS]=∀∃∃/FONT#26=cmsy6[XGP,SYS]=/FONT#28=cmtitl[XGP,SYS]=ABDEMNORSUU/FONT#29=cmssb[XGP,SYS]=.13CDEINORSTUXabell/FONT#30=cmss12[XGP,SYS]=ACEHPRTT/FONT#31=cmss8[XGP,SYS]=()125679AEGHJMNOUVWY←←/FONT#32=cmsss8[XGP,SYS]=,.AKLSTabcdefghiklmnoprstuvwxyy